不曉得有沒有人和我一樣發現本題答案每 20016 個就會發生一循環 XD
Code 如下：
#include
int f[20016];
int main(){
int n,i;
f[0]=1;f[1]=1;
for(i=2;i<20016;i++)f[i]=(f[i-1]+f[i-2])%10007;
while(scanf("%d",&n)==1)printf("%d\n",f[n%20016]);
return 0;
}
當然無論如何還是 O(log n) 的演算法比較快。
2
這種循環本來就是可預見的 ...
以前在類似題目也這樣ac過 XD
但是不實際 無法運用於所有題目
另外, O(1) 當然比O(log n)快 ..
那應該可以先跑一次找出規律後
再用mod吧? code 如下:
#include<stdio.h>
int main(){int a,b,c,d;
while(scanf("%d",&a)!=EOF){
d=0;
b=1;
c=2;
int i;
int x[100000];
x[1]=1;
x[2]=2;
for(i=3;;i++){
x[i]=x[i-1]+x[i-2];
x[i]=x[i]%10007;
if(x[i-1]==1 && x[i]==2)break; }
a=a%(i-2);
if (i%3==2){d=c+b;
d=d%10007;}
if (i%3==0){b=c+d;
b=b%10007;}
if (i%3==1){c=d+b;
c=c%10007;}
} if(a%3==0)printf("%d\n",b);
if(a%3==1)printf("%d\n",c);
if(a%3==2)printf("%d\n",d);
} return 0;
}