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;
}