本原串

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 580    Accepted Submission(s): 202

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

 

 

从反面思考：

代码：

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 #include 
           
             5 using namespace std; 6 #define mod 2008 7 #define ll int 8 int a[100000001]={
      0}; 9 ll exp_mod(ll a,ll n)//(a^n)%b10 {11     ll t;12     if(n==0)13         return 1;14     t=exp_mod(a,n/2);15     t=t*t%mod;16     if((n&1)==1)17         t=t*a%mod;18     return t;19 }20 int fun(int n)21 {22     int i,j;23     if(a[n])24     {25         return a[n];26     }27     int an=exp_mod(2,n)-2;28     for(i=2; i<=sqrt(n) ;i++)29         if(n%i==0)30         {31             an-=fun(i);32             if(i!=n/i)33             an-=fun(n/i);34             an%=mod;35         }36     return (an+mod)%mod;37 }38 int main()39 {40     int n;41     a[1]=a[2]=2,a[3]=6,a[4]=12;42     while(~scanf("%d",&n))43     {44         printf("%d\n",fun(n));45     }46 }