HDU 2197 本原串

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

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<functional>
using namespace std;
const int maxn = 10005;
const int base=2008;
map<int,int> M;
int n;

int get(int x)
{
    int i,j,k;
    for (i=x,j=2,k=1;i;i>>=1)
    {
        if (i&1) (k*=j)%=base;
        (j*=j)%=base;
    }
    return k;
}

int work(int x)
{
    if (!M.count(x))
    {
        int ans=(get(x)-2)%base;
        for (int i=2,k=sqrt(1.0*x);i<=k;i++)
        if (x%i==0) 
        {
            (ans-=work(i))%=base;
            if (i*i<x) (ans-=work(x/i))%=base;
        }
        M[x]=(ans+base)%base;
    }
    return M[x];
}

int main()
{
    M[1]=2;
    while (~scanf("%d", &n)) cout<<work(n)<<endl;
    return 0;
}