Giving the N, can you tell me the answer of F(N)?
Input
Each test case contains a single integer N(1<=N<=10^9). The input is terminated by a set starting with N = 0. This set should not be processed.
Output
For each test case, output on a line the value of the F(N)%2009.
Sample Input
Sample Output
1
7
20
对于这个题，刚开始想到的是直接暴力模拟，可看到10^9，呵呵，不超，也得拖死哈！这种题，一般都有规律，看到2009，可能就是一个关键！答案70%是一个循环，写好提交，果然不出所料~
找规律，发现4018=2009*2刚好是一个循环，解决问题！然而真羡慕那个15ms的！代码如下：
1 #include<iostream>
2 int q(int n)
3 {
4 if(n==1)return 1;
5 if (n==2)return 7;
6 else return (q(n-2)-(n-1)*(n-1)*(n-1)+n*n*n)%2009;
7 }
8 int main()
9 {
10 int n;
11 int a[4020];
12 for (int i=1;i<=4018;i++)
13 {
14 a[i]=q(i)%2009;
15 }
16 while (scanf("%d",&n)&&n!=0)
17 {
18 printf("%d\n",a[n%4018]);
19 }
20 return 0;
21 }
22
posted on 2010-12-29 10:13
路修远 阅读(239)
评论(0) 编辑 收藏 引用