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