fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MOD 1000000007
  4. #define ULL unsigned long long 
  5. void mul(ULL a[][2] , ULL b[][2])
  6. {
  7.     ULL res[2][2];
  8.     memset(res , 0 , sizeof res);
  9.     for(int i = 0 ; i < 2 ; i ++)
  10.         for(int j = 0 ; j < 2 ; j++)
  11.             for(int k = 0 ; k < 2 ; k++)
  12.                 res[i][j] = (res[i][j] + a[i][k]*b[k][j]) % MOD;
  13.     for(int i = 0 ; i < 2 ; i++)
  14.         for(int j = 0 ; j < 2 ; j++)
  15.             a[i][j] = res[i][j];
  16. }
  17. ULL  power( ULL  n)
  18. {
  19.     ULL  fib[2][2] = { {1 , 1} , { 1 , 0}},temp[2][2] = { {1 , 0 } , { 0 , 1}};
  20.     while(n)
  21.     {
  22.         if(n&1)
  23.             mul(temp , fib);
  24.         mul(fib , fib);
  25.         n>>=1;
  26.     }
  27.     return temp[0][1];
  28. }
  29. int main()
  30. {
  31.     int t;
  32.     cin>>t;
  33.     while(t--)
  34.     {
  35.         ULL l , r;
  36.         cin>>l>>r;
  37.         cout<<power(r+2)<<endl<<power(l+2)<<endl;
  38.         cout<<(power(r+2) - power(l+2) + MOD)%MOD<<endl;
  39.     }
  40.     return 0;
  41. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
4
0 0
0 3
3 5
10 19
stdout
copy 
1
1
0
5
1
4
13
5
8
10946
144
10802
https://ideone.com/HVrQRP
language:
C++14 (gcc 8.3)
created:
8 years 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!