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
很容易看出来，100100不是本原串是因为它由两个100组成，而100为3位，100100为6位，因为3是6的因子，因此可以得到：
a[n]=2^n-a[k] (其中k为n的因子）因为n比较大，求2^n 08需要用到快速幂，取因子只能开销根号n的时间复杂度，不然会超时。
#include<iostream> #include<cstdio> using namespace std; int a[100000005]; long long mod_pow(long long m,long long n,int mod) //快速幂取模 { long long ans=1; while(n) { if(n%2) ans=ans*m%mod; m=m*m%mod; n/=2; } return ans; } int solve(long long n) { if(a[n]!=0) return a[n]; a[n]=mod_pow(2,n,2008)-2; for(int i=2;i*i<=n;i++) //取因子 { if(n%i==0) { a[n]=(a[n]-solve(i)+2008)%2008; if(i*i!=n) //如果不是开方因子，就顺便把另一半求出来 a[n]=(a[n]-solve(n/i)+2008)%2008; } } return a[n]; } int main() { a[0]=0,a[1]=2,a[2]=2; int n; while(scanf("%d",&n)!=EOF) { if(n>2) a[n]=solve(n); printf("%d\n",a[n]); } return 0; }