hdu 2197

地址：http://acm.hdu.edu.cn/showproblem.php?pid=2197

题意：中文。

mark：这题一看题感觉应该是简单题，但是想了挺久。

一开始看到是这种单输入单输出的，而且n达到10^9那么大，想了一下应该是公式，没啥好的思路，就果断打表，然后丢到oeis.org里，结果发现根本没公式。

后来思考了一下，因为每个串所有可能肯定是2^n，设{i1,i2...im}是n的所有因数，可知非本源串的个数是2^n - sum{f[i1],f[i2]...f[im]}。其中f[i]代表长度为i的非本源串个数。这样只要枚举一下递归就可以了。

犹豫了很久没写，总觉得复杂度很大。后来写完以后测了一下10^9，跑了4秒才出来。调了一下才发现，时间主要花费在重复计算，因为n的所有因数的因数组成一个集合，会重复算很多次。例如100000000里有因数2，100000000的一个因数50000000也有因数2，50000000的因数有很多也含有2，这样f[2]会被计算很多次！

解决的方法是算出所有因数的非本源串值存在dp数组里，用的时候如果算过了就直接取（本质上是记忆化搜索）。因为n的因数不会超过sqrt(n)*2个，也就是不会超过20000个，所以感觉复杂度还可以。

代码：

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int dp[2][10010] ;
 6 int n ;
 7 
 8 
 9 int qpow(int a, int b)
10 {
11     int r = 1 ;
12     while (b)
13     {
14         if (b&1) r = (r*a)%2008 ;
15         a = (a*a)%2008 ;
16         b >>= 1 ;
17     }
18     return r ;
19 }
20 
21 
22 int gao(int x)
23 {
24     int i, sum = 2, flag ;
25     int xx ;
26     if (x == 1 || x == 2) return 2 ;
27     
28     if (x <= 10000) flag = 0, xx = x ;
29     else flag = 1, xx = n/x ;
30     
31     if (dp[flag][xx]!=-1) return dp[flag][xx] ;
32     
33     for (i = 2 ; i*i <= x ; i++)
34     {
35         if (x % i == 0)
36         {
37             sum += gao(i) ;
38             if (i*i != x) sum += gao(x/i) ;
39         }
40         sum %= 2008 ;
41     }
42     return dp[flag][xx] = (qpow(2,x)-sum+2008)%2008 ;
43 }
44 
45 
46 int main ()
47 {
48     while (~scanf ("%d", &n))
49     {
50         memset (dp, -1, sizeof(dp)) ;
51         printf ("%d\n", gao(n)) ;
52     }
53     return 0 ;
54 }