hdu-2197 本原串---枚举因子+容斥定理

题目链接：

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

题目大意：

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

解题思路：

设长度为i的串的个数为f(i)，显然有f(i) = 2 ^ i

长度为i的本原串为g(i)，i的所有因子t长度的本原串均可构成长度为i的非本原串，且不会重复，因为本原串定义就是不会由其他所构成

所以可得：g(i) = f(i) - ∑g(t)(t|i)

可以处理出所有因子，从小到大求出g(i)即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll pow(ll a, ll b, ll m)
 5 {
 6     ll ans = 1;
 7     a %= m;
 8     while(b)
 9     {
10         if(b & 1)ans = ans * a % m;
11         b /= 2;
12         a *= a;
13         a %= m;
14     }
15     return ans;
16 }
17 ll a[10005], b[10005];
18 int main()
19 {
20     ll n, k, m = 2008;
21     while(cin >> n && n)
22     {
23         int tot = 0;
24         for(int i = 1; i * i <= n; i++)
25         {
26             if(n % i == 0)
27             {
28                 a[tot++] = i;
29                 if(i * i != n)a[tot++] = n / i;
30             }
31         }
32         sort(a, a + tot);
33         for(int i = 0; i < tot; i++)b[i] = pow(2, a[i], m);
34         for(int i = 0; i < tot; i++)
35         {
36             for(int j = i + 1; j < tot; j++)
37             {
38                 if(a[j] % a[i] == 0)b[j] -= b[i], b[j] %= m;
39                 //此处相减可能为负值，这是因为全部模上2008的结果，所以需要每次计算后模上2008，保证绝对值在2008以内
40             }
41         }
42         cout<<(b[tot-1] + m) % m<<endl;//之前已经保证绝对值在m之内，加上m一定是正数再取模
43     }
44     return 0;
45 }