Problem Description 由0和1組成的串中，不能表示為由幾個(gè)相同的較小的串連接成的串，稱為本原串，有多少個(gè)長為n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因?yàn)樗怯蓛蓚€(gè)100組成，而1101是本原串。

?

Input 輸入包括多個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)一行，包括一個(gè)整數(shù)n，代表串的長度。

?

Output 對于每個(gè)測試數(shù)據(jù)，輸出一行，代表有多少個(gè)符合要求本原串，答案mod2008.

?

Sample Input 1 2 3 4

?

Sample Output 2 2 6 12

?

Author scnu

?

Recommend lcy???|???We have carefully selected several similar problems for you:??2196?2193?2195?1798?2159? 很有意思的題目，求出所有的排列，然后減去任何可以整除它的數(shù)的情況，最后減去2，全部0或全部1就是答案。 代碼： #include <iostream> #include <cstring> #include <cstdio> #define MAX 110000 #define mod 2008 using namespace std; int quick_pow(int a,int b) {int d = 1;a %= mod;while(b) {if(b % 2) d = (d * a) % mod;a = (a * a) % mod;b /= 2;}return d; } int getans(int n) {if(n <= 2) return 2;int ans = quick_pow(2,n);for(int i = 2;i * i <= n;i ++) {if(n % i == 0) {ans -= getans(i);if(n / i != i) ans -= getans(n / i);}}ans -= 2;if(ans < 0) ans += abs(ans / 2008 - 1) * 2008;///全程取余 可能會(huì)是負(fù)數(shù)，要取正return ans % mod; } int main() {int n;while(~scanf("%d",&n)) {printf("%d\n",getans(n));} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/8023spz/p/9827493.html

總結(jié)

以上是生活随笔為你收集整理的hdu 2197 本原串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。