HDU 2197 本原串快速幂取模+递推-白红宇

HDU 2197 本原串快速幂取模+递推

阅读量：3904 次

发布时间：2019-05-23

本文共 984 字，大约阅读时间需要 3 分钟。

Problem Description

由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？

答案mod2008.

例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。

Input

输入包括多个数据，每个数据一行，包括一个整数n，代表串的长度。

Output

对于每个测试数据，输出一行，代表有多少个符合要求本原串，答案mod2008.

Sample Input

Sample Output

代码及注释如下：

/*此题是求本元串的个数....长度为n的由0,1组成的字符串一共有2^n个.所以只要求出不是本元串的个数就可以了...一开始以为此题只与素因子有关,但是想到8的时候发现并不是...百度了一波题解,发现原来有递推关系....递推关系为:len[n]=2^n-len[x]. x为n的因子.... */#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       using namespace std;int n;map
        
         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;}