fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #define ll unsigned long long
  5. using namespace std;
  6. long double fi=(1.0/sqrt(5.0)),f2=(1.0+sqrt(5.0))/2.0,f3=(1.0-sqrt(5.0))/2.0;
  7. long double mod=1000000007.0;
  8. long double pot(long double base,ll exp){
  9.     long double res=1.0;
  10.     while(exp>0){
  11.         if(exp&1)res=fmod(fmod(res,mod)*fmod(base,mod),mod);
  12.         base=base*base;
  13.         exp>>=1;
  14.     }
  15.     return fmod(res,mod);
  16. }
  17. long double fibon(ll n){
  18.     if(n<=2)return 1;
  19.     return fmod(fi*fmod(fmod(pot(f2,n),mod)-fmod(pot(f3,n),mod),mod),mod);
  20. }
  21. int main(){
  22.     int t;
  23.     scanf("%d",&t);
  24.     for(int i=0;i<t;++i){
  25.         int n;
  26.         scanf("%d",&n);
  27.         printf("%.0Lf\n",fibon(n));
  28.     }
  29.     return 0;
  30. }
  31.  
Success #stdin #stdout 0s 16048KB
comments (?)
stdin
copy 
2
10
10000
stdout
copy 
55
409737631
https://ideone.com/1YWAdG
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!