『算法-ACM 竞赛-数学-数论』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 的串最多组成 $2^N$种情况的串，当串全部为 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 之外还有六种，我们发现恰好为，其本原串的数量。
因此此题公式为：

$2^N-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]);
        }
    }
}