程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU - 2197 本原串

HDU - 2197 本原串

編輯：C++入門知識

HDU - 2197 本原串


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 
#include 
#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;
const int mod = 2008;

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




  1. 上一頁:
  2. 下一頁:
C++入門知識
HDU1035:Robot Motion

Problem Description A rob
C語言遞歸實現二叉樹的先序、中序、後序遍歷，遞歸二叉樹

C語言遞歸實現二叉樹的先序、中序、後序遍歷，遞歸二叉樹 1

HDU 3127 WHUgirls(完全背包)

HDU 3127 WHUgirls(完全背包) &nbs
uva - UVA 1388 - Graveyard (數學推理）

題意：有一個周長為10000的圓上等距分布著n個雕塑，
C語言結構體裡的成員數組和指針(1)

單看這文章的標題，你可能會覺得好像沒什麼意思。你先別下這個
count number更正

[cpp]   項目：輸出數字出現個數 &n
相關文章
閱讀排行榜
HDU - 3416 Marriage Match IV （最大流） hdu1546-Idiomatic Phrases Gamehttp C++ list用法，list用法 TYVJ P2065(區間嵌套與統計） 1 。 LightOJ 1234 打表法（數據太大，把數據縮小100倍），lightoj1234 C++溫習-標准庫-map C++引用筆記，引用筆記 HDU 2571 命運 UVALive 6908---Electric Bike(DP或記錄型深搜)，electricbike BZOJ 1458 士兵占領 Dinic最大流 C++中的優先級隊列使用范例
熱門圖文
在C#及.NET框架中使用StringBuilder類操作字符串的技巧 C#中使用HttpWebRequest類調用WEB服務的示例 C++編程對緩沖區的理解 數據表-c#中，數據庫刪除問題 自己實現簡單的RSA秘鑰生成與加解密(Java )，rsajava 學點C語言(40):函數 - 多參函數 POI操作Excel設置前景色背景色 PHP判斷數組Array的維度(已封裝函數)
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved