Number Sequence

http://acm.hdu.edu.cn/showproblem.php?pid=1005

找循环节。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=52;
 4 int f[N];
 5 int main()
 6 {
 7     int a,b,n;
 8     while(~scanf("%d%d%d",&a,&b,&n))
 9     {
10         int s,e;
11         if (a==0&&b==0&&n==0)
12             break;
13         f[0] = 1;
14         f[1] = 1;
15         f[2] = 1;
16         for (int i = 3; i <= n; i++)
17         {
18             f[i] = (a*f[i-1]+b*f[i-2])%7;
19             for (int j = 2; j < i; j++)
20             {
21                 if (f[i]==f[j]&&f[i-1]==f[j-1])
22                 {
23                     s = j;
24                     e = i;
25                     goto RL;
26                 }
27             }
28         }
29         printf("%d
",f[n]);
30         continue;
31 RL:
32         printf("%d
",f[s+(n-e)%(e-s)]);
33     }
34     return 0;
35 }

View Code

用java写了一下，果断的超时了。。

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 
 4 public class Main {
 5 
 6     public static void main(String[] args) {
 7 
 8         Scanner cin = new Scanner(System.in);
 9         BigInteger M = BigInteger.valueOf(7);
10         while (cin.hasNext()) {
11             BigInteger a = cin.nextBigInteger();
12             BigInteger b = cin.nextBigInteger();
13             BigInteger n = cin.nextBigInteger();
14             int s1 = a.compareTo(BigInteger.ZERO);
15             int s2 = b.compareTo(BigInteger.ZERO);
16             int s3 = n.compareTo(BigInteger.ZERO);
17             if (s1 == 0 && s2 == 0 && s3 == 0)
18                 break;
19             BigInteger f1 = BigInteger.ONE;
20             BigInteger f2 = BigInteger.ONE;
21             BigInteger cnt = BigInteger.valueOf(2);
22             BigInteger f;
23             while (true) {
24                 f = a.multiply(f2).add(b.multiply(f1)).mod(M);
25                 f1 = f2;
26                 f2 = f;
27                 cnt = cnt.add(BigInteger.ONE);
28                 s1 = n.compareTo(cnt);
29                 if (s1 == 0)
30                     break;
31             }
32             System.out.println(f);
33 
34         }
35     }
36 
37 }
38

View Code