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 ;

 }