杭电ACM 1005解决思路

杭电ACM 1005

#include <stdio.h>

long int Calculate(long int n, int a, int b);
int GetT(int, int);

int main()
{
long int n;
int a, b;

printf("%d\n", GetT(1, 2));

while(1)
{
scanf("%d", &a);
scanf("%d", &b);
scanf("%ld", &n);
if (!a && !b && !n) break;
printf("%ld\n", Calculate(n, a, b));
}

return 1;
}

long int Calculate(long int n, int a, int b)
{
long int result;
long int first = 1;
long int second = 1;
long int i;
n %= GetT(a, b);
if (!n) n = GetT(a, b); 

if (n == 1 || n == 2) return 1;

for (i = 3; i <= n; i++)
{
result = (a * second + b * first) % 7;
first = second;
second = result;
}

return result;
}

int GetT(int a, int b)
{
int first = 1, second = 1;
int i;
int temp;
for (i = 3; i <= 52; i++)
{
temp = (a * second + b * first) % 7;
first = second;
second = temp;
if (first == second && first == 1) return i - 2;
}

return -1;
}

这段代码WA了.求指点 。。以下为题目地址 http://acm.hdu.edu.cn/showproblem.php?pid=1005

[解决办法]
楼主，算法有问题，这题好像是找规律的

参考：
http://www.google.com.hk/search?q=hdu+1005&opt-webpage=on&client=aff-360daohang&hl=zh-CN&ie=gb2312&newwindow=1
[解决办法]
楼主的算法是由问题的。提供我的代码给你参考下。由于(n1+n2)%n=((n1%n)+(n2%n))%n，所以数据是循环的。

C/C++ code

#include <stdio.h>#include <math.h>int  a[50];int x;int y;int n;int input ( ){   scanf("%d%d%d",&x,&y,&n);}int value(int x,int y,int n){    int i;    a[1]=1;a[2]=1;    for(i=3;i<49;i++)    {        a[i]=(x*a[i-1]+y*a[i-2])%7;    }}int main (){    int i,c,m;    while (input(x, y, n))    {        if(x!=0&&y!=0&&n!=0)        {            value(x, y, n);            m=n%48;            printf("%d\n",a[m]);        }        else        break;    }}
[解决办法]
看下这个：
C/C++ code
#include<stdio.h> #define M 52 int main() {     int a,b,n,i,f[M]={0,1,1},t;     while(scanf("%d %d %d",&a,&b,&n),a!=0||b!=0||n!=0)     {         a%=7;b%=7;         for(i=3;i<M;i++)         {              f[i]=a*f[i-1]+b*f[i-2];              f[i]%=7;             if(f[i-1]==f[3]&&f[i]==f[4]&&i>4) break;         }          t=i-4; //周期         if(n<4)printf("%d\n",f[n]);                 else printf("%d\n",f[(n-4)%t+4]); //注意，并不是f[n%t]      }     return 0; }
[解决办法]
C/C++ code
#include <iostream>using namespace std;int seq[50];int main()            {    int A,B,n,i;    while(scanf("%d%d%d",&A,&B,&n) && A+B+n)        {        seq[1]=seq[2]=1;        for(i=3;i<50;i++)            {            seq[i]=(A*seq[i-1]+B*seq[i-2])%7;            if(seq[i]==1 && seq[i-1]==1)                break;        }        n%=(i-2);        if(n==0)            cout<<seq[i-2]<<endl;        else            cout<<seq[n]<<endl;    }    return 0;}