HDU 2197本原列(数学)

本原串
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 408    Accepted Submission(s): 129
Problem Description
0と1からなる列のうち、同じ小さな数の列でつながっている列を表すことはできません.本原列と呼ばれ、n(n<=1億円)の本原列がいくつありますか.
答えmod 2008.
例えば、100100は元の列ではない.彼は2つの100から構成され、1101は元の列であるからである.
 
 
Input
入力には複数のデータが含まれ、各データの行には整数nが含まれ、列の長さを表す.
 
 
Output
各テストデータについて、1行出力し、要求に合致する本列がいくつあるかを表し、答えmod 2008.
 
 
Sample Input
1
2
3
4
 
 
Sample Output
2
2
6
12
 
 
Author
scnu
 
 
Recommend
lcy
 
 
 
この問題は比較的おもしろい問題だ.
長さnの01列の総数は2^n.であり,総数が非本原列を減らす限り,本原列が要求される.
非元の列は元の列から得ることができる.
f[n]=2^n -  和を求める(f[i]) -2  ここで、iはnの2以上の約数である.
 
約数を探すときは、2からsqrt(n)まで列挙します.iが見つかったので、n/iは約数に違いありません.
 
具体的にはコードを見てみましょう.
 

/*

* G++ 0ms 336K

*/



#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <iostream>

#include <string>

#include <map>

using namespace std;



const int MOD=2008;

map<int,int>mp;

int pow_m(int a,int n)

{

    int ret=1;

    int tmp=a%MOD;

    while(n)

    {

        if(n&1)

        {

            ret*=tmp;

            ret%=MOD;

        }

        tmp*=tmp;

        tmp%=MOD;

        n>>=1;

    }

    return ret;

}

int get(int x)

{

    if(mp[x]!=0)return mp[x];

    if(x==1)return mp[x]=2;

    int ans=pow_m(2,x);

    ans-=2;

    ans%=MOD;

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

    {

        if(x%i!=0)continue;

        if(i*i==x)

        {

            ans-=get(i);

            ans%=MOD;

        }

        else

        {

            ans-=get(i);

            ans-=get(x/i);

            ans%=MOD;

        }

    }

    return mp[x]=(ans+MOD)%MOD;

}

int main()

{

    int n;

    while(scanf("%d",&n)==1)

    {

        printf("%d
",get(n));

    }

    return 0;

}

 
 
 
 
 
コード2:

/*

*G++  15ms  360K

*/



#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <iostream>

#include <string.h>

#include <map>

using namespace std;



const int MOD=2008;

int a[10010];

int pow_m(int a,int n)

{

    int ret=1;

    int tmp=a%MOD;

    while(n)

    {

        if(n&1)

        {

            ret*=tmp;

            ret%=MOD;

        }

        tmp*=tmp;

        tmp%=MOD;

        n>>=1;

    }

    return ret;

}

int get(int x)

{

    if(x<=10000&&a[x]!=0)return a[x];

    if(x==1)return 2;

    int ans=pow_m(2,x);

    ans-=2;

    ans%=MOD;

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

    {

        if(x%i!=0)continue;

        if(i*i==x)

        {

            ans-=get(i);

            ans%=MOD;

        }

        else

        {

            ans-=get(i);

            ans-=get(x/i);

            ans%=MOD;

        }

    }

    return (ans+MOD)%MOD;

}

int main()

{

    int n;

    memset(a,0,sizeof(a));

    for(int i=1;i<=10000;i++)a[i]=get(i);

    while(scanf("%d",&n)==1)

    {

        printf("%d
",get(n));

    }

    return 0;

}