数学--数论--HDU 2197 本原串 (推规律）

由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的串最多组成 2N2^N2N种情况的串，当串全部为1或为0的时候不是本原串。

再举个例子，6的时候 6可以由三个长度为2的串组成，也可以由长度为3的两个穿组成，那么长度为2的组成方式其实是有四种00 01 10 11因为00 11组成的是全为1的或者，全为0的之前考虑过，所以不重复计算。在考虑长度为3的串，000 001 010 011 100 101 110 111 除了000 111之外还有六种，我们发现恰好为，其本原串的数量。

因此此题公式为：

2N−cal[i]其中i为因子，cal()为长度为i的本原串的数量2^N-cal[i] 其中i为因子，cal()为长度为i的本原串的数量2N−cal[i]其中i为因子，cal()为长度为i的本原串的数量

故可写出代码：

#include <cstring>

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <map>

using namespace std;

int m[10000000];

long long  n,ans;

long long  mod_pow(long long  x,long long  n,int mod)

{

    long long  res=1;

    while(n)

    {

        if(n&1)

            res=res*x%mod;

        x=x*x%mod;

        n>>=1;

    }

    return res;

}

int cal(long long  n)

{

    if(m[n]!=0)

        return m[n];

    m[n]=mod_pow(2,n,2008)-2;

    for(int i=2;i*i<=n;i++)

    {

        if(n%i==0)

        {

            m[n]=(m[n]-cal(i)+2008)%2008;

            if(i*i!=n)

                m[n]=(m[n]-cal(n/i)+2008)%2008;

        }

    }

    return m[n];

}

int main()

{

    m[0]=0;

    m[1]=2;

    m[2]=2;

    while(scanf("%d",&n)!=EOF)

    {

        if(n<=2)

            printf("%d\n",m[n]);

        else

        {

            m[n]=cal(n);

            printf("%d\n",m[n]);

        }

    }

}

巴特西

数学--数论--HDU 2197 本原串 (推规律）

2N−cal[i]其中i为因子，cal()为长度为i的本原串的数量2^N-cal[i] 其中i为因子，cal()为长度为i的本原串的数量2N−cal[i]其中i为因子，cal()为长度为i的本原串的数量

最新文章

热门文章