1005 Number Sequence-谢先斌的博客

1005 Number Sequence.

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

程序代码

C

#include <stdio.h>

int main()
{
    int a1[50];
    int i, a, b, c;
    while ( scanf( "%d%d%d", &a, &b, &c ) != EOF && (a != 0 || b != 0 || c != 0) )
    {
        a   = a % 7;
        b   = b % 7;
        a1[0]   = 1;
        a1[1]   = 1;
        for ( i = 2; i < 48; i++ )
            a1[i] = (a1[i - 2] * b + a1[i - 1] * a) % 7;
        c = cH;
        printf( "%d\n", a1[c - 1] );
    }
    return(0);
}

C++

#include
using namespace std;

int main()
{
       int a, b, n, i
       int f[49];
       f[1]=1;
       f[2]=1;
       while(cin>>a>>b>>n)
       {
              if(a==0 && b==0 && n==0)
                     break;
              for(i=3; i<49; i++)
                     f[i]=(a*f[i-1]+b*f[i-2])%7;
              f[0]=f[48];
              cout<<f[nH]<<endl;
       }
       return 0;
}

排错

可能会出现 Compilation Error、Time Limit Exceeded、Memory Limit Exceeded 等提示错误，但从以下的大量实例中可以得到规律：每48组为一个循环。

a[1]=1  a[2]=1  a[3]=3  a[4]=5  a[5]=4  a[6]=0  a[7]=1  a[8]=1  a[9]=3
a[10]=5  a[11]=4  a[12]=0  a[13]=1  a[14]=1  a[15]=3  a[16]=5  a[17]=4
a[18]=0  a[19]=1  a[20]=1  a[21]=3  a[22]=5  a[23]=4  a[24]=0  a[25]=1  a[26]=1
a[27]=3  a[28]=5  a[29]=4  a[30]=0  a[31]=1  a[32]=1  a[33]=3  a[34]=5  a[35]=4
a[36]=0  a[37]=1  a[38]=1  a[39]=3  a[40]=5  a[41]=4  a[42]=0  a[43]=1  a[44]=1
a[45]=3  a[46]=5  a[47]=4  a[48]=0  a[49]=1  a[50]=1  a[51]=3  a[52]=5  a[53]=4
a[54]=0  a[55]=1  a[56]=1  a[57]=3  a[58]=5  a[59]=4  a[60]=0  a[61]=1  a[62]=1
a[63]=3  a[64]=5  a[65]=4  a[66]=0  a[67]=1  a[68]=1  a[69]=3  a[70]=5  a[71]=4
a[72]=0  a[73]=1  a[74]=1  a[75]=3  a[76]=5  a[77]=4  a[78]=0  a[79]=1  a[80]=1
a[81]=3  a[82]=5  a[83]=4  a[84]=0  a[85]=1  a[86]=1  a[87]=3  a[88]=5  a[89]=4
a[90]=0  a[91]=1  a[92]=1  a[93]=3  a[94]=5  a[95]=4  a[96]=0  a[97]=1  a[98]=1
a[99]=3  a[100]=5  a[101]=4  a[102]=0  a[103]=1  a[104]=1  a[105]=3  a[106]=5
a[107]=4  a[108]=0  a[109]=1  a[110]=1  a[111]=3  a[112]=5  a[113]=4  a[114]=0
a[115]=1  a[116]=1  a[117]=3  a[118]=5  a[119]=4  a[120]=0  a[121]=1  a[122]=1
a[123]=3  a[124]=5  a[125]=4  a[126]=0  a[127]=1  a[128]=1  a[129]=3  a[130]=5
a[131]=4  a[132]=0  a[133]=1  a[134]=1  a[135]=3  a[136]=5  a[137]=4  a[138]=0
a[139]=1  a[140]=1  a[141]=3  a[142]=5  a[143]=4  a[144]=0  a[145]=1  a[146]=1
a[147]=3  a[148]=5  a[149]=4  a[150]=0  a[151]=1  a[152]=1  a[153]=3  a[154]=5
a[155]=4  a[156]=0  a[157]=1  a[158]=1  a[159]=3  a[160]=5  a[161]=4  a[162]=0
a[163]=1  a[164]=1  a[165]=3  a[166]=5  a[167]=4  a[168]=0  a[169]=1  a[170]=1
a[171]=3  a[172]=5  a[173]=4  a[174]=0  a[175]=1  a[176]=1  a[177]=3  a[178]=5
a[179]=4  a[180]=0  a[181]=1  a[182]=1  a[183]=3  a[184]=5  a[185]=4  a[186]=0
a[187]=1  a[188]=1  a[189]=3  a[190]=5  a[191]=4  a[192]=0  a[193]=1  a[194]=1
a[195]=3  a[196]=5  a[197]=4  a[198]=0  a[199]=1  a[200]=1  a[201]=3  a[202]=5
a[203]=4  a[204]=0  a[205]=1  a[206]=1  a[207]=3  a[208]=5  a[209]=4  a[210]=0
a[211]=1  a[212]=1  a[213]=3  a[214]=5  a[215]=4  a[216]=0  a[217]=1  a[218]=1
a[219]=3  a[220]=5  a[221]=4  a[222]=0  a[223]=1  a[224]=1  a[225]=3  a[226]=5
a[227]=4  a[228]=0  a[229]=1  a[230]=1  a[231]=3  a[232]=5  a[233]=4  a[234]=0
a[235]=1  a[236]=1  a[237]=3  a[238]=5  a[239]=4  a[240]=0  a[241]=1  a[242]=1
a[243]=3  a[244]=5  a[245]=4  a[246]=0  a[247]=1  a[248]=1  a[249]=3  a[250]=5
a[251]=4  a[252]=0  a[253]=1  a[254]=1  a[255]=3  a[256]=5  a[257]=4  a[258]=0
a[259]=1  a[260]=1  a[261]=3  a[262]=5  a[263]=4  a[264]=0  a[265]=1  a[266]=1
a[267]=3  a[268]=5  a[269]=4  a[270]=0  a[271]=1  a[272]=1  a[273]=3  a[274]=5
a[275]=4  a[276]=0  a[277]=1  a[278]=1  a[279]=3  a[280]=5  a[281]=4  a[282]=0
a[283]=1  a[284]=1  a[285]=3  a[286]=5  a[287]=4  a[288]=0  a[289]=1  a[290]=1
a[291]=3  a[292]=5  a[293]=4  a[294]=0  a[295]=1  a[296]=1  a[297]=3  a[298]=5
a[299]=4  a[300]=0  a[301]=1  a[302]=1  a[303]=3  a[304]=5  a[305]=4  a[306]=0
a[307]=1  a[308]=1  a[309]=3  a[310]=5  a[311]=4  a[312]=0  a[313]=1  a[314]=1
a[315]=3  a[316]=5  a[317]=4  a[318]=0  a[319]=1  a[320]=1  a[321]=3  a[322]=5
a[323]=4  a[324]=0  a[325]=1  a[326]=1  a[327]=3  a[328]=5  a[329]=4  a[330]=0
a[331]=1  a[332]=1  a[333]=3  a[334]=5  a[335]=4  a[336]=0  a[337]=1  a[338]=1
a[339]=3  a[340]=5  a[341]=4  a[342]=0  a[343]=1  a[344]=1  a[345]=3  a[346]=5
a[347]=4  a[348]=0  a[349]=1  a[350]=1  a[351]=3  a[352]=5  a[353]=4  a[354]=0
a[355]=1  a[356]=1  a[357]=3  a[358]=5  a[359]=4  a[360]=0  a[361]=1  a[362]=1
a[363]=3  a[364]=5  a[365]=4  a[366]=0  a[367]=1  a[368]=1  a[369]=3  a[370]=5
a[371]=4  a[372]=0  a[373]=1  a[374]=1  a[375]=3  a[376]=5  a[377]=4  a[378]=0
a[379]=1  a[380]=1  a[381]=3  a[382]=5  a[383]=4  a[384]=0  a[385]=1  a[386]=1
a[387]=3  a[388]=5  a[389]=4  a[390]=0  a[391]=1  a[392]=1  a[393]=3  a[394]=5
a[395]=4  a[396]=0  a[397]=1  a[398]=1  a[399]=3  a[400]=5

1005 Number Sequence