首页 > 代码库 > HDU - 2197 本原串

HDU - 2197 本原串

2024-07-31 17:36:55   219人阅读

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的约数就行了，当然还有考虑全0和全1的情况

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
typedef long long ll;
using namespace std;
const int mod = 2008;

map<int, int > mp;

int pow_mod(int a, int n) {
	int ans = 1;
	int tmp = a;
	while (n) {
		if (n & 1) 
			ans = ans * tmp % mod;
		tmp = tmp * tmp % mod;
		n >>= 1;
	}
	return ans;
}

int cal(int x) {
	if (mp[x] != 0) return mp[x];
	if (x == 1) return mp[x] = 2;
	int ans = pow_mod(2, x);
	ans = (ans - 2 + mod) % mod;
	for (int i = 2; i*i <= x; i++) {
		if (x % i != 0) continue;
		if (i * i == x) {
			ans -= cal(i);
			continue;
		}
		else {
			ans = (ans - cal(i) + mod) % mod;
			ans = (ans - cal(x/i) + mod) % mod;
		}
	}
	return mp[x] = (ans + mod) % mod;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		printf("%d\n", cal(n));
	}
	return 0;
}




HDU - 2197 本原串


联系
我们