Ser1ousSAM

Fib_Log(N)

Sep 30th, 2020
56
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. typedef unsigned long long ull;
  5. vector<vector<ull>> matrix_multiply(vector<vector<ull>>& A, vector<vector<ull>> B, ull& mod) {
  6.     vector<vector<ull>> C = { {0, 0}, {0, 0} };
  7.     C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod;
  8.     C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod;
  9.     C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod;
  10.     C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod;
  11.     return C;
  12. }
  13. vector<ull> decomp(ull n, vector<ull>& divs) {
  14.     while (n != 0) {
  15.         if (n % 2 == 0) {
  16.             divs.push_back(0);
  17.             n /= 2;
  18.         }
  19.         else {
  20.             divs.push_back(1);
  21.             n--;
  22.         }
  23.        
  24.     }
  25.     return divs;
  26. }
  27. vector<vector<ull>> pow(vector<vector<ull>> x, ull n, vector<vector<ull>> I, ull& mod) {
  28.     if (n == 0) return I;
  29.     else if (n == 1) return x;
  30.     else {
  31.         vector<ull> divs;
  32.         divs = decomp(n, divs);
  33.         for (ull i = divs.size() - 1; i > 0; i--) {
  34.             if (divs [i-1] == 0) x = matrix_multiply(x, x, mod);
  35.             else  x = matrix_multiply(x, I, mod);
  36.         }
  37.     }
  38.     return x;
  39. }
  40.  
  41. ull fib(ull n, ull& mod) {
  42.     vector<vector<ull>>F = { {1, 1}, {1, 0} };
  43.     F = pow(F, n, F, mod);
  44.     return F[0][1];
  45. }
  46.  
  47. int main()
  48. {
  49.     ull n, mod;
  50.     cin >> n >> mod;
  51.     cout << fib(n, mod);
  52.     return 0;
  53. }
  54.  
RAW Paste Data