本原串
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是本原串。
答案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]);
}
}
}