hdu 2197 求长度为n的本原串 (快速幂+map)

Problem Description
由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。

Input
输入包括多个数据，每个数据一行，包括一个整数n，代表串的长度。

Output
对于每个测试数据，输出一行，代表有多少个符合要求本原串，答案mod2008.

Sample Input
1
2
3
4

Sample Output
2
2
6
12

长度为n的本源串=2^n-长度为n的非本源串,对于长度为n的非本源串一定是由长度为m的串循环k次得到的,所以m一定是n的约数,(n%m==0)所以只需要求到所有n的约数长度构成的本源串个数即可
公式 F[n]=2^n-ΣF[i]-2; //2包括全0 和全1 i为n的约数

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <map>
 4 # define LL long long
 5 using namespace std ;
 6 
 7 map<int,int> m ;
 8 
 9 int pow_mod(int p, int k,int mod)
10 {
11     int ans = 1;
12     while(k) {
13         if (k & 1) ans = ans * p % mod;
14         p = (LL)p*p % mod;
15         k >>= 1;
16     }
17     return ans;
18 }
19 
20 int get(int n)
21 {
22     if (m[n]!=0)
23         return m[n] ;
24     m[n] = pow_mod(2,n,2008) - 2 ;
25     for (int i = 2 ; i*i <= n ; i++)
26     {
27         if (n%i == 0)
28         {
29             m[n] = (m[n] - get(i) +2008)%2008 ;
30             if (i*i != n)
31                 m[n] = (m[n] - get(n/i)+2008)%2008 ;
32         }
33     }
34     return m[n] ;
35 }
36 
37 int main ()
38 {
39     int n ;
40     while (cin>>n)
41     {
42         m[0] = 0 ;
43         m[1] = 2 ;
44         m[2] = 2 ;
45         if (n <= 2)
46         {
47             cout<<m[n]<<endl ;
48             continue ;
49         }
50         int ans = get(n) ;
51         cout<<ans<<endl ;
52 
53     }
54 
55     return 0 ;
56 }

View Code