#include <iostream>
using namespace std;
int a,b,s[100];
struct Pair
{
int x;
int y;
}res[50];
int main()
{
int n,i,j,k;
bool flag=false;
res[0].x=res[0].y=1;
while(cin>>a>>b>>n)
{
if(!(a||b||n))return 0;
for(i=1;i<50;++i)
{
res[i].x=res[i-1].y;
res[i].y=(a*res[i-1].y+b*res[i-1].x)%7;
for(j=0;j<i-1;++j)//…………………………注意這里循環上限是i-1，這樣可以排除三個連續相等的情況。就是把循環節為1的看成2.
{
if(res[j].x==res[i].x&&res[j].y==res[i].y)
{
flag=true;
break;
}
}
if(flag)break;
}//一個循環找出循環節大小
flag=false;//……………………注意把標志還原
if(n<=j)cout<<res[n].x<<endl;//未進入循環時
else
{
if((n-j)%(i-j)==0)k=i-1;
else k=(n-j)%(i-j)+j-1;//這個式子改了很長時間，總是會出現問題。這是最終的形式
cout<<res[k].x<<endl;
}
}
return 0;
}
提交了七次終于給過了。是道數論的簡單題，不過應該用不到什么高深的知識，關鍵是找出循環節。因為對于1000000000的大小，如果不找規律的話無論如何也要超時的。分析一下，每個數僅取決于它前面的兩個，所以如果出現了相同的數對，則必出現循環。而且，每個數都是0~6之間的一個，可知不同的數對只有7*7=49個，那么只要計算出前50個數，則其中必有相同的兩對數出現。上代碼。AC之后我想知道循環是不是總是從最前面兩個數開始，于是簡單寫了一個程序，遍歷了所有的a,b(易知它們也只有49種組合)，下面是我得到的結果：
a b j i i-j
0 0 2 4 2
0 1 0 2 2
0 2 0 6 6
0 3 0 12 12
0 4 0 6 6
0 5 0 12 12
0 6 0 4 4
1 0 0 2 2
1 1 0 16 16
1 2 0 6 6
1 3 0 24 24
1 4 0 48 48
1 5 0 21 21
1 6 0 6 6
2 0 1 4 3
2 1 0 6 6
2 2 0 48 48
2 3 0 6 6
2 4 0 48 48
2 5 0 24 24
2 6 0 2 2
3 0 1 7 6
3 1 0 16 16
3 2 0 48 48
3 3 0 42 42
3 4 0 6 6
3 5 0 2 2
3 6 0 8 8
4 0 1 4 3
4 1 0 16 16
4 2 0 48 48
4 3 0 21 21
4 4 0 2 2
4 5 0 6 6
4 6 0 8 8
5 0 1 7 6
5 1 0 6 6
5 2 0 48 48
5 3 0 2 2
5 4 0 48 48
5 5 0 24 24
5 6 0 14 14
6 0 1 3 2
6 1 0 16 16
6 2 0 2 2
6 3 0 24 24
6 4 0 48 48
6 5 0 42 42
6 6 0 3 3
可見當a,b都是7的倍數時，循環從第三個數開始（以后都是0）；當a,b中只有一個是7的倍數時，循環從第二個數開始（1,0、0,1的情況比較特殊，因為跟開始的1,1重復了所以可以認為是從第一個數開始）；當a,b都不是7的倍數是，循環從第一個數開始。可見還是從第一個數開始循環的多。循環節也有長有短，比如當a=1,b=4時一直到第49個數才出現循環。
posted on 2010-11-18 17:00
cometrue 閱讀(1507)
評論(2) 編輯 收藏 引用