由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的串最多组成 2 N 2^N 2N种情况的串，当串全部为1或为0的时候不是本原串。 再举个例子，6的时候 6可以由三个长度为2的串组成，也可以由长度为3的两个穿组成，那么长度为2的组成方式其实是有四种00 01 10 11因为00 11组成的是全为1的或者，全为0的之前考虑过，所以不重复计算。在考虑长度为3的串，000 001 010 011 100 101 110 111 除了000 111之外还有六种，我们发现恰好为，其本原串的数量。 因此此题公式为：
2N−cal[i]其中i为因子，cal()为长度为i的本原串的数量
故可写出代码：
代码语言：javascript复制#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int m[10000000];
long long n,ans;
long long mod_pow(long long x,long long n,int mod)
{
long long res=1;
while(n)
{
if(n&1)
res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
int cal(long long n)
{
if(m[n]!=0)
return m[n];
m[n]=mod_pow(2,n,2008)-2;
for(int i=2;i*i<=n;i )
{
if(n%i==0)
{
m[n]=(m[n]-cal(i) 2008) 08;
if(i*i!=n)
m[n]=(m[n]-cal(n/i) 2008) 08;
}
}
return m[n];
}
int main()
{
m[0]=0;
m[1]=2;
m[2]=2;
while(scanf("%d",&n)!=EOF)
{
if(n<=2)
printf("%dn",m[n]);
else
{
m[n]=cal(n);
printf("%dn",m[n]);
}
}
}
