1 #include<stdio.h> 2 int main() 3 { 4 int f[200],a,b,n,i; 5 while(scanf("%d%d%d",&a,&b,&n),a||b||n) 6 { 7 if(n>2) 8 { 9 f[1]=f[2]=1; 10 for(i=3;i<200;i++) 11 { 12 f[i]=(a*f[i-1]+b*f[i-2])%7; 13 if(f[i-1]==1&&f[i]==1) 14 break; 15 } 16 i-=2;//LPP，最小正周期 17 n=n%i;//比如1~5是个循环周期，f(6)=f(1)、 18 if(n==0) 19 printf("%d\n",f[i]); 20 else 21 printf("%d\n",f[n]); 22 } 23 else 24 printf("1\n"); 25 } 26 return 0; 27 }
//有个错觉，既然n是一亿，又怎么能用整形输入呢，必须需字符串，实际上是错误的，2^31-1达到
了21亿
//和递归相比主要是求出了LPP，减少了不必要的运算次数
//栈耗尽，因为n可以到一亿
#include<stdio.h>
int Calc_n(int A,int B,int n)
{
int m,p;
if(1==n||2==n)
return 1;
else
{
m=A*Calc_n(A,B,n-1);
p=B*Calc_n(A,B,n-2);
return (m%7+p%7)%7;
}
}
int main()
{
int A,B,n;int ans;
while(scanf("%d%d%d",&A,&B,&n),A||B||n)
ans=Calc_n(A,B,n);
printf("%d\n",ans);
return 0;
}
(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
很明显这是一道找规律的题目。
用到模数的一个性质 (a*b)%m=(a%m * b%m)%m, (a+b)%m=(a%m+b%m)%m
由此 f(n)=(A%7*f(n-1)+B%7*f(n-2))%7
虽然1 <= A, B <= 1000，但是A%7与B%7的值的范围只有0~6,也就是说共有49种情况，代入个数手工
推算一下，可以发现
f(n)会出现循环（这个是必然的）
}
