题意：由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。
f[n]=2^n - 求和(f[i]) -2 其中i是n的大于等于2的约数。 那个-2是由0和1组成的串
一开始写数组，直接超了，没想到这里居然可以用map，新技能
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 2008
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
//int f[MAXN]; 这样就会超内存
map<int,int> f;
int pow_m(int a,int n)
{
int ret=;
int tmp=a%MOD;
while(n)
{
if(n&)
{
ret*=tmp;
ret%=MOD;
}
tmp*=tmp;
tmp%=MOD;
n>>=;
}
return ret;
}
int fun(int x)
{
if(f[x]!=) return f[x];
if(x==) return f[x]=;
int sum=pow_m(,x);
sum%=MOD;
sum-=;
for(int i=;i*i<=x;i++)
{
if(x%i==)
{
if(i*i==x)
{
sum-=fun(i);
sum=(sum+MOD)%MOD;
}
else
{
sum-=fun(i);
sum-=fun(x/i);
sum=(sum+MOD)%MOD;
}
}
}
return f[x]=(sum+MOD)%MOD;
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
f.clear();
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",fun(n));
}
}