fork download 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define endl "\n"
  4. #define NAME "tenbai"
  5. using namespace std;
  6.  
  7. // Your large MOD
  8. const int MOD = 123456789987654321;
  9.  
  10. // Define a 2x2 Matrix structure
  11. struct Matrix {
  12.     int mat[2][2];
  13.     Matrix() {
  14.         mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
  15.     }
  16. };
  17.  
  18. // Function to multiply two matrices
  19. Matrix multiply(Matrix A, Matrix B) {
  20.     Matrix C;
  21.     for (int i = 0; i < 2; i++) {
  22.         for (int j = 0; j < 2; j++) {
  23.             for (int k = 0; k < 2; k++) {
  24.                 // CRITICAL: Use __int128_t to prevent overflow during multiplication
  25.                 // because MOD * MOD exceeds long long range.
  26.                 __int128_t val = (__int128_t)A.mat[i][k] * B.mat[k][j];
  27.                 C.mat[i][j] = (C.mat[i][j] + (int)(val % MOD)) % MOD;
  28.             }
  29.         }
  30.     }
  31.     return C;
  32. }
  33.  
  34. // Function to calculate A^p using Binary Exponentiation (Exponentiation by Squaring)
  35. Matrix power(Matrix A, int p) {
  36.     Matrix res;
  37.     // Identity matrix
  38.     res.mat[0][0] = 1; res.mat[0][1] = 0;
  39.     res.mat[1][0] = 0; res.mat[1][1] = 1;
  40.  
  41.     A.mat[0][0] %= MOD;
  42.     A.mat[0][1] %= MOD;
  43.     A.mat[1][0] %= MOD;
  44.     A.mat[1][1] %= MOD;
  45.  
  46.     while (p > 0) {
  47.         if (p & 1) res = multiply(res, A);
  48.         A = multiply(A, A);
  49.         p >>= 1;
  50.     }
  51.     return res;
  52. }
  53.  
  54. int32_t main() {
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.  
  58.     if (fopen(NAME".inp", "r")) {
  59.         freopen(NAME".inp", "r", stdin);
  60.         freopen(NAME".out", "w", stdout);
  61.     }
  62.  
  63.     int n;
  64.     if (!(cin >> n)) return 0;
  65.  
  66.     // Handle base cases manually
  67.     if (n == 0) {
  68.         cout << 0 << endl;
  69.         return 0;
  70.     }
  71.     if (n == 1) {
  72.         cout << 1 << endl;
  73.         return 0;
  74.     }
  75.  
  76.     // Base Matrix:
  77.     // [1 1]
  78.     // [1 0]
  79.     Matrix T;
  80.     T.mat[0][0] = 1; T.mat[0][1] = 1;
  81.     T.mat[1][0] = 1; T.mat[1][1] = 0;
  82.  
  83.     // We need T^(n-1) to get the nth term
  84.     T = power(T, n - 1);
  85.  
  86.     // The result is roughly F(n) = T.mat[0][0] * F(1) + T.mat[0][1] * F(0)
  87.     // Since F(1)=1, F(0)=0, the answer is just T.mat[0][0]
  88.     cout << T.mat[0][0] << endl;
  89.  
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/i5j5mz
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!