posts - 14,  comments - 11,  trackbacks - 0

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
1 2 3 0

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 路修远 阅读(247) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

转载,请标明出处!谢谢~~

常用链接

留言簿(1)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

  • 1. re: HDU 2433 最短路
  • @test
    的确这组数据应该输出20的
  • --YueYueZha
  • 2. re: HDU 2433 最短路
  • 这方法应该不对。 看下面这组数据
    4 4
    1 2
    2 3
    3 4
    2 4

    画个图,删去最后一条边 2 4 后的结果应该是20,但是此方法的输出是19
  • --test
  • 3. re: HDU 2433 最短路
  • ans = ans + sum_u + sum_v - sum[u] - sum[v],
    这个公式不是很理解啊,不知道博主怎么想的啊,谢谢咯
  • --姜
  • 4. re: HDU 2433 最短路
  • @attacker
    the i-th line is the new SUM after the i-th road is destroyed
  • --路修远
  • 5. re: HDU 2433 最短路
  • 你这样可以AC????删除<U,V>不仅改变 u,v最短路啊、、、求解
  • --attacker

阅读排行榜

评论排行榜