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

代码及注释如下：

/*
此题是求本元串的个数....
长度为n的由0,1组成的字符串一共有2^n个.
所以只要求出不是本元串的个数就可以了...
一开始以为此题只与素因子有关,但是想到8的时候发现并不是...
百度了一波题解,发现原来有递推关系....
递推关系为:
len[n]=2^n-len[x].
x为n的因子....
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int n;
map<int,int>ma;
int fastpow (int a,int b)
{
    int sum=1;
    while (b>0)
    {
        if(b&1)
           sum=sum*a%2008;
        b>>=1;
        a=a*a%2008;
    }
    return sum;
}
int Div (int x)
{
    if(x==1)
        return 2;
    if(ma.find(x)!=ma.end())
         return ma[x];
    int sum=fastpow(2,x);
    for (int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
           sum=(sum-Div(i)+2008)%2008;
           if(i*i!=x)
                sum=(sum-Div(x/i)+2008)%2008;
        }
    }
    return ma[x]=(sum+2006)%2008;
}
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
       printf("%d\n",Div(n));
    }
    return 0;
}