hdu2197 - c++编程基础 - C语言编程开发

TOP

hdu2197

2014-11-23 21:46:31 来源: 作者: 【大中小】浏览:8次

本原串
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 445 Accepted Submission(s): 145

Problem Description
由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-长度为n的本源串,对于长度为n的本源串一定是由长度为m的串循环k次得到的,所以m一定是n的约数,所以只需要求到所有n的约数长度构成的非本源串个数即可(不能求构成串之和,因为可能重复相加了,比如x是m的约数,则x一定是n的约数,则m的串包含x,只能m得非本源串+x的非本源串)所以n的非本源串个数sum[n]=2^n-(sum[x1]+sum[x2]+....sum[m]+...)-2;//x1,x2...m...是n的不为1的约数

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define INF 99999999   
using namespace std;  
  
const int MAX=10000+10;  
const int mod=2008;  
  
int pow(int a,int b){  
    int sum=1;  
    while(b){  
        if(b&1)sum=(sum*a)%mod;  
        a=(a*a)%mod;  
        b>>=1;  
    }  
    return sum;  
}  
  
int get(int n){  
    if(n == 1)return 2;//返回本源串个数   
    int sum=0;  
    for(int i=2;i*i<=n;++i){  
        if(n%i == 0){  
            sum=(sum+get(i))%mod;  
            if(n/i != i)sum=(sum+get(n/i))%mod;  
        }  
    }  
    return (pow(2,n)-sum-2+mod)%mod;  
}  
  
int main(){  
    int n;  
    while(cin>>n){  
        cout<
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 99999999
using namespace std;

const int MAX=10000+10;
const int mod=2008;

int pow(int a,int b){
	int sum=1;
	while(b){
		if(b&1)sum=(sum*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return sum;
}

int get(int n){
	if(n == 1)return 2;//返回本源串个数
	int sum=0;
	for(int i=2;i*i<=n;++i){
		if(n%i == 0){
			sum=(sum+get(i))%mod;
			if(n/i != i)sum=(sum+get(n/i))%mod;
		}
	}
	return (pow(2,n)-sum-2+mod)%mod;
}

int main(){
	int n;
	while(cin>>n){
		cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU4521：小明系列问题――小明序..	下一篇：HDU 2051 Bitset

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: