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的本源串=2^n-长度为n的非本源串,对于长度为n的非本源串一定是由长度为m的串循环k次得到的,所以m一定是n的约数,(n%m==0)所以只需要求到所有n的约数长度构成的本源串个数即可
公式 F[n]=2^n-ΣF[i]-2; //2包括 全0 和全1 i为n的约数
# include <iostream>
# include <cstdio>
# include <map>
# define LL long long
using namespace std ; map<int,int> m ; int pow_mod(int p, int k,int mod)
{
int ans = ;
while(k) {
if (k & ) ans = ans * p % mod;
p = (LL)p*p % mod;
k >>= ;
}
return ans;
} int get(int n)
{
if (m[n]!=)
return m[n] ;
m[n] = pow_mod(,n,) - ;
for (int i = ; i*i <= n ; i++)
{
if (n%i == )
{
m[n] = (m[n] - get(i) +)% ;
if (i*i != n)
m[n] = (m[n] - get(n/i)+)% ;
}
}
return m[n] ;
} int main ()
{
int n ;
while (cin>>n)
{
m[] = ;
m[] = ;
m[] = ;
if (n <= )
{
cout<<m[n]<<endl ;
continue ;
}
int ans = get(n) ;
cout<<ans<<endl ; } return ;
}