HDU 2197 本源串

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

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

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

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

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

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

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

 #include <stdio.h>
 #include <string.h>
 #include <iostream>
 #include <queue>
 #include <vector>
 #include <algorithm>
 #include <stack>
 #include <set>
 #include <map>
 #include <math.h>
 #define pb push_back
 #define CLR(a) memset(a, 0, sizeof(a));
 #define MEM(a, b) memset(a, b, sizeof(a));
 #define fi first
 #define se second using namespace std; typedef long long ll; const int MAXN = ;
 const int MAXV = ;
 const int MAXE = ;
 const int INF = 0x3f3f3f3f;
 const ll MOD = ; int n; ll mypow(ll t, int x)
 {
     ll tmp;
     if (x == ) return ;
     tmp = mypow(t, x >> ) % MOD;
     if (x & ) tmp = (t*tmp*tmp) % MOD;
     else tmp = (tmp*tmp) % MOD;
     return tmp;
 } vector<int> getfac(int x)
 {
     vector<int> v;
     for(int i = ; i*i <= x; i++)
     {
         if (x % i ==  && x != i)
         {
             v.pb(i);
             if (x / i != i && x / i != x) v.pb(x/i);
         }
     }
     return v;
 }
 ll a[MAXN];
 ll fun(int x)
 {
     if (a[x] != ) return a[x];
     vector<int> v = getfac(x);
     ll ret = mypow(, x);
     for (int i = ; i < v.size(); i++)
     {
         a[v[i]] = fun(v[i]);
         ret = (ret + MOD - a[v[i]]) % MOD;
     }
     return ret % MOD;
 } int main()
 {
     //freopen("in.txt", "r", stdin);
     int m = ;
     while (~scanf("%d", &n))
     {
         if (a[n] == )
         {
             a[n] = fun(n) % MOD;
         }
         printf("%lld\n", a[n]);
     }
     return ;
 }