本原串（HDU 2197 快速幂）

时间：2024-01-15 08:19:26

本原串

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1091    Accepted Submission(s): 350

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
F[n]=2^n-F[k],k为n的约数。
此题用反面情况求解，长度为n的串有2^n中，减去非本原串，非本原串肯定是由长度为v字串不断重复u次得到的，那么v必然是n的约数。
感觉很长时间没做题了脑袋笨了不少，约数枚举法忘了。不然肯定超时
 #include <cstring>

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <map>

 using namespace std;

 typedef long long LL;

 map<int,int> m;

 map<int,int>::iterator ite;

 LL n,ans;

 LL mod_pow(LL x,LL n,int mod)

 {

     LL res=;

     while(n)

     {

         if(n&)

             res=res*x%mod;

         x=x*x%mod;

         n>>=;

     }

     return res;

 }

 int cal(LL n)

 {

     int i,j;

     if(m[n]!=)

         return m[n];

     m[n]=mod_pow(,n,)-;

     for(i=;i*i<=n;i++)

     {

         if(n%i==)

         {

             m[n]=(m[n]-cal(i)+)%;    //不然可能是负数

             if(i*i!=n)

                 m[n]=(m[n]-cal(n/i)+)%;

         }

     }

     return m[n];

 }

 int main()

 {

     m[]=;

     m[]=;

     m[]=;

     //freopen("in.txt","r",stdin);

     while(scanf("%d",&n)!=EOF)

     {

         if(n<=)

             printf("%d\n",m[n]);

         else

         {

             m[n]=cal(n);

             printf("%d\n",m[n]);

         }

     }

 }

相关文章