Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 175657 Accepted Submission(s): 43409
Problem Description
A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n).
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
Output
For each test case, print the value of f(n) on a single line.
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5
Author
CHEN, Shunbao
Source
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1005
分析:这道题按照公式写了一发,结果
(⊙o⊙)…看了下题目才知道,数字范围很大,就算不是这个错误也会T了QAQ,看了下网上的这种解法,以48为周期的解法,其实大于48的整数都可以!
1 #include <bits/stdc++.h>
2 using namespace std;
3 int f[55];
4 int main()
5 {
6 int a,b,n;
7 f[1]=1;
8 f[2]=1;
9 while(scanf("%d%d%d",&a,&b,&n)&&a&&b&&n)
10 {
11 int T=0;
12 for(int i=3;i<=51;i++)
13 f[i]=(a*f[i-1]+b*f[i-2])%7;
14 cout<<f[n%51]<<endl;
15 }
16 }
但是,但是,,,,,,这种解法是存在问题的,我以51为周期也会过,只能说后台数据太水了,随便拿一组数据去测48为周期,比如7,7,50/51,输出结果应该为0,但是输出会等于1,明显解法是错误的,于是就有以下两种解法:
方法一:很容易想到有规律 打表也能看出有规律 但是对于每组 A,B规律却不一样 循环节不同 我一开始是找的从第一个数据开始的循环节 但是循环节不一定从第一个位置开始 所以我的毫无疑问会错!
下面给出第一种解法的AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 int f[100000005];
4 int main()
5 {
6 int a,b,n,t;
7 f[1]=1;
8 f[2]=1;
9 while(scanf("%d%d%d",&a,&b,&n)&&a&&b&&n)
10 {
11 int T=0;
12 for(int i=3;i<=n;i++)
13 {
14 f[i]=(a*f[i-1]+b*f[i-2])%7;
15 for(int j=2;j<i;j++)
16 {
17 if(f[i-1]==f[j-1]&&f[i]==f[j])
18 {
19 T=i-j;
20 t=j;
21 break;
22 }
23 }
24 if(T>0)
25 break;
26 }
27 if(T>0)
28 {
29 f[n]=f[(n-t)%T+t];
30 }
31 cout<<f[n]<<endl;
32 }
33 return 0;
34 }
方法二:鸽巢原理,请参看鸽巢原理
因为f[i]只能取0~7,下面的程序用mp[x][y],记录f[i]的值x y相邻时候出现过,鸽巢原理知,状态总数不会超过7*7!
下面给出AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 int f[105],mp[8][8];
4 int main()
5 {
6 int n,a,b,k,x,y;
7 while(scanf("%d%d%d",&a,&b,&n)&&a&&b&&n)
8 {
9 memset(mp,0,sizeof(mp));
10 f[1]=1;
11 f[2]=1;
12 x=1;
13 y=1;
14 k=3;
15 while(!mp[x][y])
16 {
17 mp[x][y]=k;
18 f[k]=(a*y+b*x)%7;
19 y=(a*y+b*x)%7;
20 x=f[k-1];
21 k++;
22 }
23 int h=mp[x][y];
24 if(n<k)
25 {
26 printf("%d\n",f[n]);
27 }
28 else printf("%d\n",f[(n-h)%(k-h)+h]);
29 }
30 return 0;
31 }