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，呵呵，不超，也得拖死哈！這種題，一般都有規(guī)律，看到2009，可能就是一個關鍵！答案70%是一個循環(huán)，寫好提交，果然不出所料~
找規(guī)律，發(fā)現(xiàn)4018=2009*2剛好是一個循環(huán)，解決問題！然而真羨慕那個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
路修遠 閱讀(250)
評論(0) 編輯 收藏 引用