hdu2197

本原串
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<iostream>   
#include<cstdio>   
#include<cstdlib>   
#include<cstring>   
#include<string>   
#include<queue>   
#include<algorithm>   
#include<map>   
#include<iomanip>   
#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<<get(n)<<endl;  
    }  
    return 0;  
}  

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#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<<get(n)<<endl;
	}
	return 0;
}

补充：软件开发 , C++ ,

上一个：poj 2255 Tree Recovery
下一个：HDU4521：小明系列问题——小明序列(LIS加强版)