HDU 2197 本源串

如果一个串能完全由其子串组成，那么这个串就不是本源串

求长度为n的本源串的个数。

由定义一个串如果不是本源串，那么他的长度一定是组成其子本源串的长度的(>=1) 整数倍。

那么长度为n的串总个数是2^n个

枚举n 的因子长度为n的本源串的个数就是2^n - a[k1]-a[k2]-..(k1 k2..是n的非n因子)。

因为n可以非常的大，所以需要快速幂，不能直接打表，求因子的复杂度是根号n

所以在线算，查，记忆化一下还是很快的。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <queue>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <stack>
 8 #include <set>
 9 #include <map>
10 #include <math.h>
11 #define pb push_back
12 #define CLR(a) memset(a, 0, sizeof(a));
13 #define MEM(a, b) memset(a, b, sizeof(a));
14 #define fi first
15 #define se second
16 
17 using namespace std;
18 
19 typedef long long ll;
20 
21 const int MAXN = 100000007;
22 const int MAXV = 207;
23 const int MAXE = 207;
24 const int INF = 0x3f3f3f3f;
25 const ll MOD = 2008;
26 
27 int n;
28 
29 ll mypow(ll t, int x)
30 {
31     ll tmp;
32     if (x == 0) return 1;
33     tmp = mypow(t, x >> 1) % MOD;
34     if (x & 1) tmp = (t*tmp*tmp) % MOD;
35     else tmp = (tmp*tmp) % MOD;
36     return tmp;
37 }
38 
39 vector<int> getfac(int x)
40 {
41     vector<int> v;
42     for(int i = 1; i*i <= x; i++)
43     {
44         if (x % i == 0 && x != i) 
45         {
46             v.pb(i);
47             if (x / i != i && x / i != x) v.pb(x/i);
48         }
49     }
50     return v;
51 }
52 ll a[MAXN];
53 ll fun(int x)
54 {
55     if (a[x] != 0) return a[x];
56     vector<int> v = getfac(x);
57     ll ret = mypow(2, x);
58     for (int i = 0; i < v.size(); i++)
59     {
60         a[v[i]] = fun(v[i]);
61         ret = (ret + MOD - a[v[i]]) % MOD;
62     }
63     return ret % MOD;
64 }
65 
66 int main()
67 {
68     //freopen("in.txt", "r", stdin);
69     int m = 0;
70     while (~scanf("%d", &n))
71     {
72         if (a[n] == 0)
73         {
74             a[n] = fun(n) % MOD;
75         }
76         printf("%lld
", a[n]);
77     }
78     return 0;
79 }