本文主要是介绍HDU - 2197 本原串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。
答案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 本原串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
