首页 > ACM题库 > HDU-杭电 > hdu 2197 本原串-快速幂-[解题报告]C++
2013
12-30

hdu 2197 本原串-快速幂-[解题报告]C++

本原串

问题描述 :

由0和1组成的串中,不能表示为由几个相同的较小的串连接成的串,称为本原串,有多少个长为n(n<=100000000)的本原串?
答案mod2008.
例如,100100不是本原串,因为他是由两个100组成,而1101是本原串。

输入:

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

输出:

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

样例输入:

1
2
3
4

样例输出:

2
2
6
12

题目链接

F[n]=2^n-ΣF[i]-2;(其中,i是n的约数)

F[n]是最后的结果

按照公式直接求解就好了,今天学到了新的一招 用map来存储已经查询过的记录

下面附上题目代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<map>
using namespace std;
map<int,int>mp;
const int MOD=2008;
int fun(int a,int n){  //a的n次方
   if(n==1)return a;
   int num=fun(a,n/2);
   num=num*num%MOD;
   if(n%2==1)num=num*a%MOD;
   return (num+MOD)%MOD;    
}
int cal(int n){    计算长度为n的本原串的个数
    if(mp[n]!=0)return mp[n];
    mp[n]=fun(2,n)-2;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
              mp[n]=(mp[n]-cal(i)+MOD)%MOD;
              if(i*i!=n)mp[n]=(mp[n]-cal(n/i)+MOD)%MOD;     
           }           
             
    }
   return mp[n];   //用map来存储
}



int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
       mp[0]=0;
       mp[1]=2;
       mp[2]=2;
       if(n<=2){cout<<mp[n]<<endl;continue;}
       int ans=cal(n);
       cout<<ans<<endl;                                   
    }    
    return 0;
}

竟然发现 用 10000000的数组可以过掉。。。。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
const int L=100000010;
int a[100000010]={0};
using namespace std;
int fun(int n){
    if(n==1)return 2;
    int num=fun(n/2);
    if(n%2==1)return num=num*num*2%2008;
    else return num*num%2008;
}

int cal(int n){
     if(a[n]!=0)return a[n];
     int ans=fun(n)-2;
     int edge=(int)sqrt(n);
     for(int i=2;i*i<=n;i++){
       if(n%i==0){
            if(i*i==n)ans=(ans-cal(i)+2008)%2008;
            else {
                ans=(ans-cal(i)+2008)%2008;
                ans=(ans-cal(n/i)+2008)%2008;     
            }        
       }  
     }
    return ans;
}



int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
       a[1]=2;
       a[2]=2;
       if(a[n]!=0)printf("%d\n",a[n]);
       else {
          a[n]=cal(n);
          printf("%d\n",a[n]);      
       }                              
    }
    return 0;    
}


解题转自:http://blog.csdn.net/worldmakewayfordream/article/details/11837603


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。