由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$種情況的串，當串全部為1或為0的時候不是本原串。
再舉個例子，6的時候 6可以由三個長度為2的串組成，也可以由長度為3的兩個穿組成，那么長度為2的組成方式其實是有四種00 01 10 11因為00 11組成的是全為1的或者，全為0的之前考慮過，所以不重復計算。在考慮長度為3的串，000 001 010 011 100 101 110 111 除了000 111之外還有六種，我們發現恰好為，其本原串的數量。
因此此題公式為：

$2^N?cal[i]其中i為因子，cal()為長度為i的本原串的數量$

故可寫出代碼：

#include <cstring> #include <iostream> #include <cstdio> #include <algorithm> #include <map> using namespace std; int m[10000000]; long long n,ans; long long mod_pow(long long x,long long n,int mod) {long long res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res; } int cal(long long n) {if(m[n]!=0)return m[n];m[n]=mod_pow(2,n,2008)-2; for(int i=2;i*i<=n;i++){if(n%i==0){m[n]=(m[n]-cal(i)+2008)%2008; if(i*i!=n)m[n]=(m[n]-cal(n/i)+2008)%2008;}}return m[n]; } int main() {m[0]=0;m[1]=2;m[2]=2;while(scanf("%d",&n)!=EOF){if(n<=2)printf("%d\n",m[n]);else{m[n]=cal(n);printf("%d\n",m[n]);}} }

總結

以上是生活随笔為你收集整理的数学--数论--HDU 2197 本原串 (推规律）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。