Untitled
raw download clone
C
views 23
,
size 1374 b
#include<stdio.h>
#define MOD 1000000007//(unsigned long long)((1e9)+7)

unsigned long long fastpow(unsigned long long *P,unsigned long long exponment)
{
     unsigned long long n = exponment;
     unsigned long long matrice[2][2]={1,1,1,0},tmp[2][2];
     int i,j;
     while(n)
     {
          if(n&1) //底數乘以次方那坨
          {
               unsigned long long tmp1=P[0],tmp2=P[1];
               for(i=0;i<2;i++)
               {
                    P[i]=((matrice[1-i][0]*tmp2)%MOD+(matrice[1-i][1]*tmp1)%MOD)%MOD;
               }
          }
          n>>=1;
          for(i=0;i<2;i++)
          {
               for(j=0;j<2;j++)
               {
                    tmp[i][j]=matrice[i][j];
               }
          }
          for(i=0;i<2;i++)
          {
               for(j=0;j<2;j++)
               {
                    matrice[i][j]=((tmp[i][0]*tmp[0][j])%MOD+(tmp[i][1]*tmp[1][j])%MOD)%MOD;
               }
          }
     }
     P[1]%MOD;
     if(P[1]<0)P[1]+=MOD;
     return P[1];
}

int main(void)
{
     unsigned long long x,P[2];

     while(scanf("%lld",&x)!=EOF)
     {
          P[0]=1;P[1]=1;
          if(x==1)printf("1\n");
          else if(x==2)printf("1\n");
          else
          {
               printf("%lld\n",fastpow(P,x-2));
          }
     }
     return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.