本原串

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1478    Accepted Submission(s): 503 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   求的是长度为n的本原串的个数，长度为n的串共有2^n种，非本原串的个数加上本原串的个数就是总个数。 非本原串就是可以分为多个相同串的串，如4可以分为1*4、2*2、4*1三种 n的因数（不包括自身）所组成的本原串的个数总数就是长度为n的串的非本原串的个数 即 ans[n] = 2^n - ∑ans[i] （i为n的因数）有点像是递推 #include<iostream> #include<stdio.h> #include<string.h> #include<math.h> using namespace std; #define LL long long LL n,mod = 2008,ans[100001000];//n<=1e8 LL qkm(LL n,LL m)//快速幂 { LL ans = 1,base = n; while(m) { if(m%2) ans*=base,ans%=mod; base*=base; base%=mod; m/=2; } return ans; } LL Ans(LL x) { if(ans[x]) return ans[x]; LL all,Not = 0; all = qkm(2,x); for(int i=2;i<=sqrt(x);i++) { if(x%i==0) { Not+=Ans(i); Not%=mod; if(i*i!=x) Not+=Ans(x/i); Not%=mod; } } return ans[x]= (all-Not+mod-2)%mod; } int main() { ans[1] = 2; while(scanf("%lld",&n)!=EOF) { printf("%lld\n",Ans(n)); } return 0; }