整理的演算法模板合集： ACM模板

點我看演算法全家桶系列！！！

實際上是一個全新的精煉模板整合計劃

紅書《題目與解讀》第一章數學題解《ACM國際大學生程式設計競賽題目與解讀》

全書目錄：《題目與解讀》紅書訓練筆記目錄《ACM國際大學生程式設計競賽題目與解讀》

紅書《題目與解讀》第一章數學題解《ACM國際大學生程式設計競賽題目與解讀》
第一章數學
- 1.1 概率
- - Problem A.Coupons （幾何概型，概率）
  - Problem B.Generator （KMP，期望，高斯消元）
  - Problem C.Dinner with Schwarzenegger!!! （概率）
- 1.2 代數
- 1.2.1 Polya
- - Problem A.Arif in Dhaka （Polya，等價類計數）
- 1.2.2 矩陣
- - Problem A.Tower
  - Problem B.XX Language
- 1.2.3 線性方程組
- - Problem A. Ars Longa
- 1.2.4 線性規劃
- - Problem A.Expensive Dirnk
- 1.3 組合
- 1.3.1 基本排列組合
- - The Unreal TournamentUVA 10207
- 1.3.2 容斥原理
- 1.3.3 生成函式
- 1.3.4 生成樹計數
- 1.3.5 綜合
- 1.4 博弈
- - Problem A. Battle for the Ring（SG函式）
  - Problem B. Fool's Game
  - Problem C. Points Game
- 1.5 數論
- 1.5.1 模線性方程
- - Problem A.Integer Sequences （多變元線性同余方程）
- 1.5.2 歐幾里得
- - Problem A.Wizards
- 1.5.3 歐拉定理
- - Problem A.Strange Limit（拓展歐拉定理）
- 1.5.4 歐拉函式
- - Problem A.GCD Determinant（ gcd ? \gcd gcd 矩陣定理）
- 1.5.5 平方剩余
- - Problem A.Square Root（二次剩余）
- 1.5.6 原根
- - Problem A.Fermat's Last Theorem
- 1.5.7 整除與剩余
- - Problem A.Brute-Force Algorithm（乘法換加法，矩陣快速冪）
  - Problem B. Interal Roots（多項式，整數）
  - Problem C.Vivian's Problem（梅森素數，狀壓DP）
- 1.5.8 中國剩余定理
- - Problem A.Voyager 1（Java高精，中國剩余定理）
- 1.6 分析
- - Problem A.Bridge

第一章數學

1.1 概率

Problem A.Coupons （幾何概型，概率）

UVA 10288

Problem

一共有 n n n 種不同的優惠券，每次得到一個優惠券的概率相同，問期望多少次得到所有 n n n 種優惠券，以帶分數的形式輸出，

Solution

方法一：

設 f [ i ] f[i] f[i] 表示已經買到 i i i 個優惠券的期望購買次數，

考慮最后一次購買，若買到的是一個新優惠券，則：

f [ i ] + = ( f [ i ? 1 ] + 1 ) × n ? ( i ? 1 ) n f[i] += (f[i-1]+1)\times \cfrac{n-(i-1)}{n} f[i]+=(f[i?1]+1)×nn?(i?1)?

若買到的是一個已經買過但不是第 i i i 個買的優惠券，則：

f [ i ] + = ( f [ i ] + 1 ) × i ? 1 n f[i]+=(f[i]+1)\times \frac{i-1}{n} f[i]+=(f[i]+1)×ni?1??

整理得：

f [ i ] = f [ i ? 1 ] + n n ? i + 1 f[i]=f[i-1]+\frac{n}{n-i+1} f[i]=f[i?1]+n?i+1n??

即：

a n s = ∑ i = 1 n n n ? i + 1 = ∑ i = 1 n n i ans = \sum_{i = 1}^{n}\cfrac{n}{n-i+1}=\sum_{i=1}^{n}\cfrac{n}{i} ans=i=1∑n?n?i+1n?=i=1∑n?in?

顯然最后的答案就是調和級數前綴和，

若資料較大的話可以 O ( 1 ) O(1) O(1) 計算調和級數前綴和：

調和級數 ∑ i = 1 ∞ 1 n \displaystyle\sum_{i = 1}^{∞}\cfrac{1}{n} i=1∑∞?n1? 的極限為 ln ? n + C \ln n+C lnn+C，其中 C = 0.57721566490153286060651209 C=0.57721566490153286060651209 C=0.57721566490153286060651209 是歐拉常數

方法二：

紅書上的題解

當前已有 k k k 種，顯然得到新優惠券的概率為 n ? k n \cfrac {n-k} n nn?k?，顯然是幾何概型，所以期望是 n n ? k \cfrac {n}{n-k} n?kn?，所以答案就是 n n + n n ? 1 + ? + n 1 = n × ∑ i = 1 n 1 i \displaystyle \cfrac n n+ \cfrac {n}{n-1}+\cdots+\cfrac{n}{1}=n\times \sum\limits_{i=1}^{n}\cfrac 1 i nn?+n?1n?+?+1n?=n×i=1∑n?i1?

Hint

資料較大，注意約分，除掉 gcd ? \gcd gcd

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
//#define ll __int128;
typedef long long ll;
const int N = 107;

int n, m;
int up[N], down[N]; 

ll lcm(int a, int b)
{
	return a / __gcd(a, b) * b;
}

int get_len(int x)
{ 
	int len = 0;
	while(x) {
		x /= 10;
		len ++ ;
	}
	return len;
}

void solve()
{
	ll LCM = 1;
	for(int i = 1; i <= n; ++ i) {
		up[i] = n;
		down[i] = i;
		LCM = lcm(LCM, i);
	}	
	ll sum = 0;
	for(int i = 1; i <= n; ++ i) {
		sum += n * (LCM / i);
	}
	ll d = __gcd(sum, LCM);
	sum /= d;
	LCM /= d;
	if(LCM == 1) {
		cout << sum << endl;
		return ;
	}
	ll mo = sum % LCM;
	ll l = sum / LCM;
	for(int i = 1; i <= get_len(l) + 1; ++ i) cout << " ";
	cout << mo << endl;
	cout << l << " ";
	for(int i = 1; i <= get_len(LCM); ++ i) cout << "-";
	puts("");
	for(int i = 1; i <= get_len(l) + 1; ++ i) cout << " ";
	cout << LCM << endl;
}

signed main()
{
	while(scanf("%lld", &n) != EOF) { 
		solve();
	}
	return 0;
}

Problem B.Generator （KMP，期望，高斯消元）

ZOJ 2619

Problem

給定一個字串 S S S 和字符集大小 n n n ，要求另生成一個字串，它一開始為空，每次平均且獨立地隨機生成一個字符集中的字符添加到其末尾，生成出字串 S S S 時停下，求所生成字串的長度的期望，

Solution

顯然生成的字串越來越長，每次由 n n n 種字符選擇，那么就有 i n i^n in 種方案數，雜亂無章的無從下手，所以從對答案的貢獻角度出發，發現對于答案而言，有用的只有最后生成的字串 T T T 的后綴與模式串 S S S 的匹配長度，因此很多雜亂的字串實際上對于答案而言是同一種狀態，即一共只有 0 ～ L 0\sim L 0～L 種狀態，表示兩字串匹配的長度，

這樣就有了清晰的狀態，考慮狀態如何轉移即可，
在這里插入圖片描述

書中倒推由于都是未知的需要使用高斯消元解方程組，比較麻煩，精度還不能得到保障，我們這里利用一個小技巧，直接正推，利用 KMP ， O ( n ) O(n) O(n) 求出失配陣列 nex i , j \text{nex}_{i,j} nexi,j?（當然要在失配的時候用）

反過來設 f[i] 為從狀態 0 0 0 到狀態 i i i 期望次數，答案顯然就是 f[len]

則可以把原轉移方程直接改寫為：

f [ i ] = f [ i + 1 ] n + 1 n ∑ j = 0 n ? 1 f [ nex [ i + ′ A ′ ] ] ? 1 f[i] = \frac{f[i+1]}{n}+\frac{1}{n}\sum_{j=0}^{n-1}{f[\text{nex}[i + 'A\ ']]} - 1 f[i]=nf[i+1]?+n1?j=0∑n?1?f[nex[i+′A ′]]?1
就是 f [ i ] f[i] f[i] 由下一步匹配成功的 f [ i + 1 ] f[i+1] f[i+1] 與未匹配成功的 ∑ j = 0 n ? 1 f [ nex [ i + ′ A ′ ] ] \displaystyle \sum_{j=0}^{n-1}{f[\text{nex}[i + 'A\ ']]} j=0∑n?1?f[nex[i+′A ′]] 減去一次期望操作轉移而來，

化簡成正推的形式即：
f [ i + 1 ] = ( f [ i ] + 1 ) × n ? ∑ j = 0 n ? 1 f [ nex [ i + ′ A ′ ] ] f[i+1] = (f[i] + 1)\times n - \sum_{j=0}^{n-1}{f[\text{nex}[i + 'A\ ']]} f[i+1]=(f[i]+1)×n?j=0∑n?1?f[nex[i+′A ′]]

初始化 f[0] = 0，然后 O ( n ) O(n) O(n) 正序遞推即可，

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 50;

int n, m, k, t, ans, kcase, cases;
int a[N];
int nex[N];
char s[N];
ll f[N];
int len;

void get_nex(char* s)
{ 
	for (int i = 2, j = 0; i <= len; ++ i) {
		while(j != 0 && s[j + 1] != s[i])
			j = nex[j];
		if(s[j + 1] == s[i])
			++ j;
		nex[i] = j;
	}
}

void solve()
{ 
	scanf("%d%s", &n, s + 1);
	len = strlen(s + 1);
	get_nex(s);
	f[0] = 0;
	for (int i =0; i <= len - 1; ++ i) {
		f[i + 1] = (f[i] + 1) * n;
		for (int j = 0; j < n; ++ j) {
			if(s[i + 1] == 'A' + j) 
				continue; 
			int pos = i;
			while(pos && s[pos + 1] != j + 'A')
				pos = nex[pos];
			if(s[pos + 1] == j + 'A')
				++ pos;
			f[i + 1] -= f[pos];
		}
	}
	printf("%lld\n", f[len]);
}

int main()
{
	scanf("%d", &t); 
	while(t -- ) {
		printf("Case %d:\n", ++ kcase);
		solve();
		if(t)
		    puts("");
	}
	return 0;
}

Problem C.Dinner with Schwarzenegger!!! （概率）

UVA10217

Problem

有若干人排隊買電影票，如果某個人的生日與排在他前面的某個人的生日相同，那么他講中獎，中獎的機會只有一個，給所有中獎者中排在最前面的那一位，排在第一位的人如果與買票者的生日相同，那么他將中獎，如果一年有 n n n 天，求排在什么位置的中獎概率最大，和理論上的最佳實數位置，

Solution

設第 i i i 個人的中獎概率是 f[i]，顯然有：

f [ 1 ] = 1 n f[1] = \cfrac 1 n f[1]=n1?

f [ 2 ] = n ? 1 n × 1 n f[2] = \cfrac{n-1}{n} \times \cfrac 1 n f[2]=nn?1?×n1?

. . . ... ...

f [ i ] = n ? 1 n × n ? 1 n × n ? 2 n × . . . × n ? i + 2 n × i ? 1 n f[i] = \cfrac{n-1}n \times \cfrac{n-1} n \times \cfrac{n-2} n \times ...\times \cfrac {n-i+2} n \times \cfrac{i-1} n f[i]=nn?1?×nn?1?×nn?2?×...×nn?i+2?×ni?1?

f [ i + 1 ] = n ? 1 n × n ? 1 n × n ? 2 n × . . . × n ? i + 1 n × i n f[i+1] = \cfrac {n-1} n \times \cfrac {n-1} n \times \frac {n-2} n \times ...\times \cfrac{n-i+1} n \times \cfrac i n f[i+1]=nn?1?×nn?1?×nn?2?×...×nn?i+1?×ni?

有

f [ i ] f [ i + 1 ] = ( i ? 1 ) × n ( n ? i + 1 ) × i \cfrac {f[i]}{f[i+1]} = \cfrac {(i-1)\times n}{(n-i+1)\times i} f[i+1]f[i]?=(n?i+1)×i(i?1)×n?

顯然概率越來越小， f [ i ] f [ i + 1 ] ≥ 1 \cfrac {f[i]}{f[i+1]} \ge 1 f[i+1]f[i]?≥1 解得：

1 ? 4 × n + 1 2 ≤ i ≤ 1 + 4 × n + 1 2 \cfrac{1-\sqrt{4\times n+1} } {2} \le i \le \cfrac{1+\sqrt{4\times n+1}} {2} 21?4×n+1 ??≤i≤21+4×n+1 ??

最佳整數位置為 ? 1 + 4 × n + 1 2 ? \left \lceil\cfrac {1+\sqrt{4\times n+1}} 2\right\rceil ?21+4×n+1 ???，最佳實數位置為 ? 1 + 4 × n + 1 2 \cfrac {-1+\sqrt{4\times n+1} }2 2?1+4×n+1 ??，

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7, maxm = maxn << 1 | 7;

int n, m, s, t;
int a[maxn];

int main()
{
	while(scanf("%d", &n) != EOF) {
		double ans = (-1.0 + sqrt(1.0 + 4.0 * n)) / 2.0;
		int ans2 = ans + 1;
		printf("%.2lf %d\n", ans, ans2);
	}
	return 0;
}

1.2 代數

1.2.1 Polya

Problem A.Arif in Dhaka （Polya，等價類計數）

UVA 10294

Problem

給你一串珠子（連接成了一個環），共有 n n n 個珠子組成，你有 t t t 種顏色，現在你來給這個珠子染色，問染成項鏈有多少種方法？染成手鐲有多少種方法？在項鏈里，經過順時針旋轉后相同的算一個，在手鐲里，經過順時針旋轉或者沿著對稱軸兌換后一樣的算一個，

Solution

Code

1.2.2 矩陣

Problem A.Tower

HDU 2971

Problem

a 1 = 1 a_1=1 a1?=1，給定 a 2 a_2 a2?，設 a n = 2 a 2 × a n ? 1 ? a n ? 2 a_n=2a_2\times a_{n-1}-a_{n-2} an?=2a2?×an?1??an?2?，求 s n = a 1 2 + a 2 2 + ? + a n 2 s_n=a_1^2+a_2^2+\cdots+a_n^2 sn?=a12?+a22?+?+an2?，

Solution

設 p = a 2 × 2 p=a_2\times 2 p=a2?×2

則有：

a n 2 = p 2 × a n ? 1 + a n ? 2 2 ? 2 × p × a n ? 1 × a n ? 2 a_n^2=p^2\times a_{n-1}+a_{n-2}^2-2\times p\times a_{n-1}\times a_{n-2} an2?=p2×an?1?+an?22??2×p×an?1?×an?2?

s n = s n ? 1 + a n 2 = s n ? 1 + p 2 × a n ? 1 2 + a n ? 2 2 ? 2 × p × a n ? 1 × a n ? 2 s_n=s_{n-1}+a_{n}^2=s_{n-1}+p^2\times a_{n-1}^2+a_{n-2}^2 -2\times p\times a_{n-1}\times a_{n-2} sn?=sn?1?+an2?=sn?1?+p2×an?12?+an?22??2×p×an?1?×an?2?

可以發現重復項 a n ? 1 2 a_{n-1}^2 an?12? 與 a n ? 1 × a n ? 2 a_{n-1}\times a_{n-2} an?1?×an?2?，可得：
a n × a n ? 1 = p × a n ? 1 2 ? a n ? 1 × a n ? 2 a_n\times a_{n-1}=p\times a_{n-1}^2 -a_{n-1}\times a_{n-2} an?×an?1?=p×an?12??an?1?×an?2?

由不變項可得：

( S n a n 2 a n ? 1 2 a n × a n ? 1 ) = ( 1 p 2 1 ? 2 p 0 p 2 1 ? 2 p 0 1 0 0 0 p 0 ? 1 ) ( S n ? 1 a n ? 1 2 a n ? 2 2 a n ? 1 × a n ? 2 ) \left(\begin{array}{c}S_n \\a_n^{2} \\a_{n-1}^{2} \\a_n \times a_{n-1}\end{array}\right)=\left(\begin{array}{cccc}1 & p^{2} & 1 & -2 p \\0 & p^{2} & 1 & -2 p \\0 & 1 & 0 & 0 \\0 & p & 0 & -1\end{array}\right)\left(\begin{array}{c}S_{n-1} \\a_{n-1}^{2} \\a_{n-2}^{2} \\a_{n-1} \times a_{n-2}\end{array}\right) ?????Sn?an2?an?12?an?×an?1???????=?????1000?p2p21p?1100??2p?2p0?1???????????Sn?1?an?12?an?22?an?1?×an?2???????

Problem B.XX Language

ZOJ 2113

1.2.3 線性方程組

Problem A. Ars Longa

UVALive 3563

1.2.4 線性規劃

Problem A.Expensive Dirnk

HDU 2979

1.3 組合

1.3.1 基本排列組合

The Unreal TournamentUVA 10207

1.3.2 容斥原理

Jackpot Gym 101648J
The Almost Lucky Number SCU 3502

1.3.3 生成函式

Vasya’s Dad URAL 1387

1.3.4 生成樹計數

Organising the OrganisationUVA 10766

1.3.5 綜合

Hero of Our TimeSGU 481

1.4 博弈

Problem A. Battle for the Ring（SG函式）

URAL 1540

Problem

給你一堆石子，每個石子都有權重，每次取一堆中的一個石子，將這堆石子中所有權重比該石子小的全部拿掉，分成若干堆新石子，不能操作的輸，

Solution

Problem B. Fool’s Game

POJ 3153

Problem

Solution

Problem C. Points Game

URAL 1397

Problem

給出平面 2 n 2n 2n 點，有兩個玩家游戲，每個回合，玩家A可以取走一個點，然后玩家B取走一個，經過 n n n 個回合沒有點了，結束比賽，一個玩家的得分是他所取走的所有兩兩之間的歐幾里得距離的和，得分最高者獲勝，A和B都是聰明人，求兩者分數之差為多少，

Solution

1.5 數論

1.5.1 模線性方程

Problem A.Integer Sequences （多變元線性同余方程）

SGU 140

Problem

給出一個長度為 n n n 的非負整數序列 A A A 和兩個數 P , B P,B P,B，要求找出同樣的非負整數序列 X X X 滿足 A 1 ? X 1 + A 2 ? X 2 + . . . + A n ? X n = B ( m o d P ) A_1*X_1 + A_2*X_2 + ...+ A_n*X_n = B \pmod P A1??X1?+A2??X2?+...+An??Xn?=B(modP)

Solution

A 1 ? X 1 + A 2 ? X 2 + . . . + A n ? X n = B ( m o d P ) A_1*X_1 + A_2*X_2 + ...+ A_n*X_n = B \pmod P A1??X1?+A2??X2?+...+An??Xn?=B(modP)

顯然有
A 1 ? X 1 + A 2 ? X 2 + . . . + A n ? X n + P Q = B , Q ∈ Z A_1*X_1 + A_2*X_2 + ...+ A_n*X_n +PQ= B,Q∈\Z A1??X1?+A2??X2?+...+An??Xn?+PQ=B,Q∈Z

看起來是一個多元一次方程，我們只需要找到一個合法的非負整數序列 X X X 作為解即可，因此我們可以構造答案，我們可以求出二元一次方程的解，因此我們可以從前往后，兩個數就可以找到一組解，這樣兩兩合并即可得到一組合法的解，

即：先考慮 A 1 X 1 + A 2 X 2 A_1X_1+A_2X_2 A1?X1?+A2?X2?，我們可以求出方程 A 1 x + A 2 y = gcd ? ( A 1 , A 2 ) A_1x+A_2y=\gcd(A_1,A_2) A1?x+A2?y=gcd(A1?,A2?) 的解 x , y x,y x,y，此時 x x x 就是滿足當前條件的 X X X 序列的第一項的解， X 1 = x , X 2 = y X_1=x,X_2=y X1?=x,X2?=y，我們把 gcd ? ( A 1 , A 2 ) \gcd(A_1,A_2) gcd(A1?,A2?) 當作新的元素，于是得到新的方程：

gcd ? ( A 1 , A 2 ) x + A 3 ? X 3 + . . . + A n ? X n + P Q = B , Q ∈ Z \gcd(A_1,A_2)x+A_3*X_3 + ...+ A_n*X_n +PQ= B,Q∈\Z gcd(A1?,A2?)x+A3??X3?+...+An??Xn?+PQ=B,Q∈Z

我們再合并 g c d ( A 1 , A 2 ) gcd(A1,A2) gcd(A1,A2) 和 A 3 A3 A3 ，解出 gcd ? ( A 1 , A 2 ) x + A 3 y = gcd ? ( gcd ? ( A 1 , A 2 ) , A 3 ) \gcd(A_1,A_2)x+A_3y=\gcd(\gcd(A_1,A_2),A_3) gcd(A1?,A2?)x+A3?y=gcd(gcd(A1?,A2?),A3?) 的 x , y x,y x,y，把之前求出的所有的 X i X_i Xi?乘上 x x x（一層一層的）， X 3 = y X_3=y X3?=y ，不斷重復，直到合并只剩兩項為止，

最后求解 gcd ? ( A 1 , A 2 , A 3 . . . A n ) x + P y \gcd(A_1,A_2,A_3...A_n)x+Py gcd(A1?,A2?,A3?...An?)x+Py 的 x , y x,y x,y，判斷 gcd ? ( A 1 , A 2 , A 3 . . . A n ) \gcd(A_1,A_2,A_3...A_n) gcd(A1?,A2?,A3?...An?) 能否整除 B B B ，若不能整除，顯然該丟番圖方程無解，輸出 N O NO NO 即可，

若能整除，所有的解乘上 B gcd ? ( A 1 , A 2 . . . A n , P ) \cfrac B {\gcd(A_1,A_2...A_n,P)} gcd(A1?,A2?...An?,P)B? 即為一組合法的解，輸出即可，

注意我們在求解 x , y x,y x,y 的程序中可能得到負數解，而題目要求輸出整數解，最后輸出的時候將 X i X_i Xi? 置于 [ 0 , P ] [0,P] [0,P] 之間即可，

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 7;
int n, m, s, t, k, ans;
int X[maxn];
int A[maxn], p, b;

int exgcd(int a, int b, int &x, int &y)
{
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, x, y);
	int z = x;
	x = y, y = z - y * (a / b);
	return d;
}

int main()
{
	scanf("%d%d%d", &n, &p, &b);
	for (int i = 1; i <= n; ++ i)
		scanf("%d", &A[i]), A[i] %= p;
	int gcd = A[1]; 
	X[1] = 1;
	for (int i = 2; i <= n; ++ i) {
		int x, y; 
		gcd = exgcd(gcd, A[i], x, y);
		for (int j = 1; j < i; ++ j)
			X[j] = X[j] * x % p;
		X[i] = y; 
	} 
	int x, y;
	gcd = exgcd(gcd, p, x, y);
	for (int i = 1; i <= n; ++ i)
		X[i] = X[i] * x % p;
	if(b % gcd != 0) {
		puts("NO");
		return 0;
	}
	else {
		puts("YES");
		for (int i = 1; i <= n; ++ i) {
			X[i] = X[i] * b / gcd % p;
			printf("%d ", (X[i] + p) % p);
		}
	}
	puts("");
	return 0;
}

1.5.2 歐幾里得

Problem A.Wizards

UVALive 4305

1.5.3 歐拉定理

Problem A.Strange Limit（拓展歐拉定理）

ZOJ 2674

Problem

定義數列 a 1 = p a_1=p a1?=p， a n + 1 = p a n ( n ≥ 1 ) a_{n+1}=p^{a_n}(n\ge 1) an+1?=pan?(n≥1)

其中 p p p 是素數，定義 b n = a n m o d ?? m ! b_n=a_n\mod m! bn?=an?modm!

要求求出： lim ? n → ∞ b n \displaystyle \lim_{n\rightarrow\infin}b_n n→∞lim?bn?

2 ≤ p , m ≤ 12 2\le p,m\le 12 2≤p,m≤12，

Solution

其實就是求 p p p p … p^{p^{p^{p^{\dots}}}} pppp…，

拓展歐拉定理遞回計算即可，

由于 m ! ≤ 4 × 1 0 8 m!\le4\times 10^8 m!≤4×108，所以我們每次需要 O ( n ) O(\sqrt n) O(n ?) 計算 φ \varphi φ，時間復雜度 O ( n n ) O(n\sqrt n) O(nn ?)，

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 7;
int n, m, s, t, k, ans;
int fact;
int p;

int qpow(int a, int b, int mod)
{
	int res = 1;
	while(b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int phi(int x)
{
	int ans = x;
	for (int i = 2; i * i <= x; ++ i) {
		if (x % i == 0) {
			ans = ans / i * (i - 1);
			while (x % i == 0) 
				x /= i;
		}
	}
	if (x > 1)
		ans = ans / x * (x - 1);
	return ans;
}

int solve(int a, int b)
{
	if(b == 1) return 0;
	int phi_b = phi(b); 
	return qpow(a, phi_b + solve(a, phi_b), b);
}

signed main()
{
	bool flag = false;
	while(scanf("%lld%lld", &p, &m) != EOF) {
		if(flag) puts("");
		else flag = true;
			
		fact = 1;
		for (int i = 1; i <= m; ++ i)
			fact = fact * i;
		cout << solve(p, fact) << endl;	
	}
	return 0;
}

1.5.4 歐拉函式

Problem A.GCD Determinant（ gcd ? \gcd gcd 矩陣定理）

UVALive 4190

Problem

給定 n n n 個數 a 1 , a 2 , a 3 ? ? , a n a_1,a_2,a_3\cdots,a_n a1?,a2?,a3??,an?，且對于任意 a i a_i ai? 的約數 d d d ， d d d 均在數集 { a i } \{a_i\} {ai?} 中，用這 n n n 個數構造一個 n × n n\times n n×n 的矩陣，其中第 i i i 行第 j j j 列的數是 a i a_i ai? 和 a j a_j aj? 的最大公約數，

求這個矩陣的行列式的值，結果模 1 0 9 + 7 10^9+7 109+7，

0 < n < 1000 , 0 < x i < 2 × 1 0 9 0<n<1000,0<x_i<2\times10^9 0<n<1000,0<xi?<2×109

Solution

顯然矩陣中的數是一些數的因子集合，

由于行列式交換兩行或者兩列以后，行列式的值會變號，因此我們可以把輸入的因子集合 { a i } \{a_i\} {ai?} 從小到大進行排序，列交換的同時，行也進行交換，因此排序后的行列式的值不變，得到一個矩陣形如：

[ gcd ? ( a 1 , a 1 ) gcd ? ( a 1 , a 2 ) gcd ? ( a 1 , a 3 ) ? gcd ? ( a 1 , a n ) gcd ? ( a 2 , a 1 ) gcd ? ( a 2 , a 2 ) gcd ? ( a 2 , a 3 ) ? gcd ? ( a 2 , a n ) ? ? ? ? ? gcd ? ( a n , a 1 ) gcd ? ( a n , a 2 ) gcd ? ( a n , a 3 ) ? gcd ? ( a n , a n ) ] \begin{bmatrix} \gcd(a_1,a_1) & \gcd(a_1,a_2) & \gcd(a_1,a_3) & \cdots&\gcd(a_1,a_n)\\ \gcd(a_2,a_1) & \gcd(a_2,a_2) & \gcd(a_2,a_3) & \cdots&\gcd(a_2,a_n)\\\vdots& \ddots& \ddots & \ddots&\vdots\\\gcd(a_n,a_1) & \gcd(a_n,a_2) & \gcd(a_n,a_3) & \cdots&\gcd(a_n,a_n) \end{bmatrix} \quad ??????gcd(a1?,a1?)gcd(a2?,a1?)?gcd(an?,a1?)?gcd(a1?,a2?)gcd(a2?,a2?)?gcd(an?,a2?)?gcd(a1?,a3?)gcd(a2?,a3?)?gcd(an?,a3?)??????gcd(a1?,an?)gcd(a2?,an?)?gcd(an?,an?)???????

其中 a i < a i + 1 a_i< a_{i+1} ai?<ai+1?，這里輸入的元素 a i a_i ai? 是封閉的，即：若 x x x 在 { a i } \{a_i\} {ai?} 中，則 x x x 的所有因子均在 { a i } \{a_i\} {ai?} 中，

計算矩陣的行列式，我們將矩陣對角化，設對角化之后，對角線上的數為 d i a g [ i ] \mathrm{diag}[i] diag[i]，顯然有：

d i a g [ i ] = a i ? ∑ j = 1 i ? 1 [ gcd ? ( a j , a i ) = = a j ? d i a g [ i ] : 0 ] \mathrm{diag}[i]=a_i-\sum_{j=1}^{i-1}[\gcd(a_j,a_i)==a_j?\mathrm{diag}[i]:0] diag[i]=ai??j=1∑i?1?[gcd(aj?,ai?)==aj??diag[i]:0]

其中 d i a g [ 1 ] = 1 \mathrm{diag}[1]=1 diag[1]=1，

直接遞推計算，時間復雜度 O ( n 2 log ? a i ) O(n^2\log a_i) O(n2logai?)，可以通過本題，

這里有一個有趣的性質，類似本題中滿足 g c d ? c l o s e d \mathrm{gcd-closed} gcd?closed 的 gcd ? \gcd gcd 矩陣的行列式等于元素的歐拉函式的乘積：

d e t = ∑ i = 1 n d i a g [ i ] = ∑ i = 1 n ( φ ( a i ) ) \mathrm{det}=\sum_{i=1}^{n}{\mathrm{diag}[i]}=\sum_{i=1}^n(\varphi(a_i)) det=i=1∑n?diag[i]=i=1∑n?(φ(ai?))

證明：在這里插入圖片描述

因此我們只需要求出每個數的歐拉函式，累乘即可，

時間復雜度 O ( n n ) O(n\sqrt{n}) O(nn ?)，

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e3 + 7, mod = 1e9 + 7;
int n, m, s, t, k, ans;
int a[maxn];
int phi(int n)
{
	int ans = n;
	for (int i = 2; i * i <= n; ++ i) {
		if (n % i == 0) {
			ans = ans / i * (i - 1);
			while (n % i == 0) 
				n /= i;
		}
	}
	if (n > 1)
		ans = ans / n * (n - 1);
	return ans;
}

signed main()
{
	while(scanf("%lld", &n) != EOF) {
		ans = 1;
		for (int i = 1; i <= n; ++ i) {
			int x;
			scanf("%lld", &x);
			ans = ans * phi(x) % mod;
		}
		cout << ans << endl;
	}
	return 0;
}

1.5.5 平方剩余

Problem A.Square Root（二次剩余）

URAL 1132

Problem

給定一個質數 p p p 以及正整數 a a a，求方程 x 2 ≡ a ( m o d p ) x^2\equiv a\pmod p x2≡a(modp) 的所有的解，

1 ≤ a , p ≤ 2 15 ? 1 1\le a,p\le 2^{15} - 1 1≤a,p≤215?1，保證 a a a ， p p p 互質，

Solution

2008年的論文題，

當年還是一個新知識，現在就是一個板子，

套用二次剩余模板即可，

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 7;

int mod;
ll I_mul_I; // 虛數單位的平方
struct Complex {//自己實作復數
	ll real, imag;
	Complex(ll real = 0, ll imag = 0): real(real), imag(imag) { }
};
inline bool operator == (Complex x, Complex y) {
	return x.real == y.real and x.imag == y.imag;
}
inline Complex operator * (Complex x, Complex y) {
	return Complex((x.real * y.real + I_mul_I * x.imag % mod * y.imag) % mod,
			(x.imag * y.real + x.real * y.imag) % mod);
}
Complex qpow(Complex x, int k) {
	Complex res = 1;
	while(k) {
		if(k & 1) res = res * x;
		x = x * x;
		k >>= 1;
	}
	return res;
}
bool check_if_residue(int x) {
	return qpow(x, (mod - 1) >> 1) == 1;
}
int solve(int n, int p) {
	n %= p, mod = p;
	if(p == 2) return n;
	ll a = rand() % mod;
	if(qpow(n,(mod - 1) / 2) == p - 1) return -1;//不存在
	while(!a || check_if_residue((a * a + mod - n) % mod))
		a = rand() % mod;
	I_mul_I = (a * a + mod - n) % mod;

	return int(qpow(Complex(a, 1), (mod + 1) >> 1).real);
}
int n, m, p, t;
int main()
{
    //srand(time(0));
    scanf("%d", &t);
    while(t -- ) {
        scanf("%d%d", &n, &p);
        int ans1 = 0, ans2 = 0;
        if(n == 0) {
            puts("0");
            continue;
        }
        ans1 = solve(n, p);
        if(ans1 == -1) puts("No root");
        else {
            ans2 = p - ans1;
            if(ans1 > ans2) swap(ans1, ans2);
            if(ans1 == ans2) printf("%d\n", ans1);
            else printf("%d %d\n", ans1, ans2);
        }
    }
    return 0;
}

1.5.6 原根

Problem A.Fermat’s Last Theorem

SGU 511

Problem

1.5.7 整除與剩余

Problem A.Brute-Force Algorithm（乘法換加法，矩陣快速冪）

HDU 3221

給定如下的遞回函式，求輸入時的 f u n n y ( ) \mathrm{funny}() funny() 函式被呼叫的次數，

在這里插入圖片描述

輸出模 p p p 的結果，

1 ≤ n ≤ 1 0 9 , 1 ≤ p ≤ 1 0 6 , 0 ≤ a , b ≤ 1 0 6 1\le n\le 10^9,1\le p\le 10^6,0\le a, b\le10^6 1≤n≤109,1≤p≤106,0≤a,b≤106

Solution

設 f ( i ) f(i) f(i) 表示輸入 i i i 時，函式被呼叫的次數，

顯然有 f ( 1 ) = a , f ( 2 ) = b f(1) = a, f(2) = b f(1)=a,f(2)=b， f [ i ] = f [ i ? 1 ] × f [ i ? 2 ] f[i] = f[i-1]\times f[i - 2] f[i]=f[i?1]×f[i?2]，

看上去就是乘法版的斐波那契數列，顯然我們可以將乘法轉化為加法，即在指數下， f ( i ) f(i) f(i) 就是一個類斐波那契數列，設 f i b ( i ) fib(i) fib(i) 表示斐波那契數列，則有 f ( i ) = a f i b ( n ? 2 ) × b f i b ( n ? 1 ) f(i) = a^{fib(n-2)}\times b^{fib(n-1)} f(i)=afib(n?2)×bfib(n?1)

本題要求的是 f ( i ) m o d ?? p = a f i b ( n ? 2 ) × b f i b ( n ? 1 ) m o d ?? p f(i)\mod p=a^{fib(n-2)}\times b^{fib(n-1)}\mod p f(i)modp=afib(n?2)×bfib(n?1)modp，

我們利用矩陣快速冪求出 f i b ( n ? 2 ) fib(n-2) fib(n?2) 和 f i b ( n ? 1 ) fib(n-1) fib(n?1) 之后，快速冪計算即可，

Code

不知道為啥wa了嗚嗚嗚…

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 7, maxm = 2;
int n, m, s, t, k, ans, kcase;
ll a, b, p;
int primes[maxn], cnt;
bool vis[maxn];
int phi[maxn];

void get_phi(int n)
{
	phi[1] = 1;
	for (int i = 2; i <= n; ++ i) {
		if (vis[i] == 0) {
			primes[ ++ cnt] = i;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= cnt && primes[j] * i <= n; ++ j) {
			vis[i * primes[j]] = 1;
			if (i % primes[j] == 0) {
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}
	}
}

void mul(ll c[], ll a[], ll b[][maxm])
{
	ll tmp[maxm] = {0};
	for (int j = 0; j < maxm; ++ j) 
		for (int k = 0; k < maxm; ++ k)
			tmp[j] = (tmp[j] + a[k] * b[k][j]) % phi[p];
	memcpy(c, tmp, sizeof tmp);
}

void mul(ll c[][maxm], ll a[][maxm], ll b[][maxm])
{
	ll tmp[maxm][maxm] = {0};
	for (int i = 0; i < maxm; ++ i)
		for (int j = 0; j < maxm; ++ j)
			for (int k = 0; k < maxm; ++ k)
				tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % phi[p];
	memcpy(c, tmp, sizeof tmp);
}

ll qpow(ll a, ll b, ll mod)
{
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
	
} 

ll Matqpow(ll n)
{
	
	ll f[maxm] = {0, 1};
	ll A[maxm][maxm] = {
		{0, 1}, 
		{1, 1},
	};
	if (n <= 2) return 1;
	while (n) {
		if (n & 1) mul(f, f, A);
		mul(A, A, A);
		n >>= 1;
	}
	return f[0] % phi[p];
}

signed main()
{
	scanf("%lld", &t);
	get_phi(maxn - 6);
	while (t -- ) {
		printf("Case #%lld: ",  ++ kcase); 
		scanf ("%lld%lld%lld%lld", &a, &b, &p, &n);
		if (n == 1) {
			printf("%lld\n", a % p);
			continue;	
		}
		else if (n == 2) {
			printf("%lld\n", b % p);
			continue;
		}
		else if (n == 3) {
			printf("%lld\n", a * b % p);
			continue;
		} 
		ll fiba = Matqpow(n - 2);
		ll fibb = Matqpow(n - 1); 
		if (fiba >= phi[p]) fiba = fiba % phi[p] + phi[p];
		if (fibb >= phi[p]) fibb = fibb % phi[p] + phi[p]; 
		ll ansa = qpow(a, fiba, p) % p;
		ll ansb = qpow(b, fibb, p) % p;
		 
		cout << ansa * ansb % p << '\n';
	}
	return 0;
}

Problem B. Interal Roots（多項式，整數）

POJ 3471

Problem

給定一個多項式 f ( x ) = x n + a n ? 1 x n ? 1 + ? + a 0 f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0 f(x)=xn+an?1?xn?1+?+a0?，求 f ( x ) = 0 f(x)=0 f(x)=0 的所有整數解，注意，重根算作不同的根，

n ≤ 100 , ∣ a i ∣ < 2 31 n\le 100, |a_i|<2^{31} n≤100,∣ai?∣<231

Solution

求所有的整數解，設一共有 m m m 個整數解： x 1 , x 2 , ? ? , x m x_1,x_2,\cdots,x_m x1?,x2?,?,xm?

則有 f ( x ) = ( x ? x 1 ) ( x ? x 2 ) ? ( x ? x m ) g ( x ) f(x)=(x-x_1)(x-x_2)\cdots(x-x_m)g(x) f(x)=(x?x1?)(x?x2?)?(x?xm?)g(x)，其中 g ( x ) g(x) g(x) 表示剩余的沒有整數解的多項式，

若不存在 g ( x ) g(x) g(x)，則顯然有 ∏ i = 1 m x i = a 0 \displaystyle \prod_{i=1}^{m}x_i=a_0 i=1∏m?xi?=a0?，

若存在 g ( x ) g(x) g(x)，設 g ( x ) g(x) g(x) 的常數項為 t t t ，則顯然有 t × ∏ i = 1 m x i = a 0 t\times \displaystyle \prod_{i=1}^{m}x_i=a_0 t×i=1∏m?xi?=a0?，

則顯然有： ∏ i = 1 m x i ∣ a 0 \displaystyle \prod_{i=1}^{m}x_i\mid a_0 i=1∏m?xi?∣a0?

因此我們就可以列舉 a 0 a_0 a0? 的所有因子 a ′ a' a′（注意因為多項式的整數解可能為負數，所以我們需要列舉的因子包括負數因子），判斷 ( x ? a ′ ) (x-a') (x?a′) 是否為 f ( x ) f(x) f(x) 的約數，其中 n ≤ 100 n\le 100 n≤100，我們只需要做暴力 O ( n 2 ) O(n^2) O(n2) 的多項式除法 f ( x ) x ? a ′ = ( x ? x 1 ) ( x ? x 2 ) ? ( x ? x m ) g ( x ) x ? a ′ \cfrac {f(x)}{x-a'}=\cfrac{(x-x_1)(x-x_2)\cdots(x-x_m)g(x)}{x-a'} x?a′f(x)?=x?a′(x?x1?)(x?x2?)?(x?xm?)g(x)? 判斷是否整除即可，若是 f ( x ) f(x) f(x) 的約數，顯然 a ′ a' a′ 是 f ( x ) f(x) f(x) 的一個整數解，或者直接帶入 x = a ′ x=a' x=a′，計算多項式的值看是否為 0 0 0 即可，

若 a 0 = 0 a_0=0 a0?=0，我們只需要將多項式 f ( x ) f(x) f(x) 除掉一個 x x x，直到 a 0 ≠ 0 a_0\neq 0 a0??=0 為止即可，注意此時 a 0 = 0 a_0=0 a0?=0 說明有一個整數解 0 0 0，

注意計算重根即可，

時間復雜度 O ( n a i ) \mathcal{O}(n\sqrt {a_i}) O(nai? ?)，

Code

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const long long maxn = 1e2 + 6, maxm = 1e5 + 7;

long long n, m, s, t, k, ans[maxm], kcase;
long long tot;
long long a[maxn];

void get(long long k)
{
	long long tmp[maxn];
	tmp[0] = a[0];
	while(n) {
		for (int i = 1; i <= n; ++ i)
			tmp[i] = a[i], a[i] = a[i - 1] * k + a[i];
		if (a[n]) {
			for (int i = 0; i <= n; ++ i)
				a[i] = tmp[i];
			break;
		}
		ans[ ++ tot] = k, n -- ;
	}
}

void solve()
{
	a[0] = 1;
	// cin >> a[n - 1], a[n - 2], ..., a[2], a[1], a[0];
	for (int i = 1; i <= n; ++ i)
		scanf("%lld", &a[i]);
	tot = 0;
	//a_0 = 0 ，多項式除 x 直到 a_0 != 0
	while(n && a[n] == 0) 
		ans[ ++ tot] = 0, n -- ;
	long long a_0 = a[n] < 0 ? -a[n] : a[n];
	int len = int(sqrt(a_0 + 0.5));
	for (int i = 1; i <= len; ++ i) {
		if (a_0 % i == 0) {
			get(i), get(-i);
			get(a_0 / i), get(-a_0 / i);
		}
	}
	cout << tot << endl;
	sort(ans + 1, ans + 1 + tot);
	for (int i = 1; i <= tot; ++ i)
		printf("%lld\n", ans[i]); 
}

int main()
{
	while(scanf("%lld", &n) != EOF) {
		solve();
	}
	return 0;
}

Problem C.Vivian’s Problem（梅森素數，狀壓DP）

ZOJ 2360

給定 k k k 個整數 q 1 , q 2 , ? ? , q k q_1,q_2,\cdots,q_k q1?,q2?,?,qk?，求一個具有如下形式的 N N N：

N = ∏ i = 1 k q i c i ( 0 ≤ c i ≤ 10 , ∑ i = 1 k c i ≥ 1 , 1 ≤ i ≤ k ) N=\prod_{i=1}^{k}q_i^{c_i}(0\le c_i\le 10,\sum_{i=1}^kc_i\ge 1,1\le i\le k) N=i=1∏k?qici??(0≤ci?≤10,i=1∑k?ci?≥1,1≤i≤k)

其中 c i c_i ci? 由你任意地制定，記 M M M 為 N N N 的所有約數的和，問是否存在一個 N N N ，使得 M M M 恰好是 2 2 2 的冪，如果沒有這樣的 N N N 存在，輸出 NO，若 M = 2 x M=2^x M=2x，則輸出 x x x；若有多個 x x x ，輸出其中最大的一個，

1 ≤ k ≤ 100 , 1 < q i < 2 31 1\le k\le 100,1<q_i<2^{31} 1≤k≤100,1<qi?<231

Solution

首先對于一個數 N N N，由唯一分解定理可得 N = p 1 a 1 p 2 a 2 ? p r a r N=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r} N=p1a1??p2a2???prar??

顯然有約數和 M = ( 1 + p 1 + p 1 2 + p 1 3 + ? + p 1 a 1 ) × ? × ( 1 + p r + p r 2 + p r 3 + ? + p r a r ) M=(1+p_1+p_1^2+p_1^3+\cdots+p_1^{a_1})\times \cdots\times (1+p_r+p_r^2+p_r^3+\cdots+p_r^{a_r}) M=(1+p1?+p12?+p13?+?+p1a1??)×?×(1+pr?+pr2?+pr3?+?+prar??)

要求 M = 2 x M=2^x M=2x，顯然該連乘式中每個括號內的 ( 1 + p i + p i 2 + p i 3 + ? + p i a i ) (1+p_i+p_i^2+p_i^3+\cdots+p_i^{a_i}) (1+pi?+pi2?+pi3?+?+piai??) 均為 2 2 2 的冪，

由于 p p p 是質數，顯然當 p = 2 p=2 p=2 時， ( 1 + p i + p i 2 + p i 3 + ? + p i a i ) = 1 + 2 × ( ? ? ) ≠ 2 x (1+p_i+p_i^2+p_i^3+\cdots+p_i^{a_i})=1+2\times (\cdots)\neq2^x (1+pi?+pi2?+pi3?+?+piai??)=1+2×(?)?=2x，

則 p p p 均為奇數，顯然括號內必然有偶數項，否則和一定是奇數，

則有

1 + p i + p i 2 + p i 3 + ? + p i a i = ( 1 + p i 2 + p i 4 + ? + p i a i ? 1 ) + ( p i + p i 3 + p i 5 + ? + p i a i ) = ( 1 + p ) ( 1 + p i 2 + p i 4 + ? + p i a i ? 1 ) \begin{aligned}&\ \ \ \ \ 1+p_i+p_i^2+p_i^3+\cdots+p_i^{a_i}&\\&=(1+p_i^2+p_i^4+\cdots+p_i^{a_{i-1}})+(p_i+p_i^3+p_i^5+\cdots+p_i^{a_i})&\\&=(1+p)(1+p_i^2+p_i^4+\cdots+p_i^{a_{i-1}})\end{aligned} ? 1+pi?+pi2?+pi3?+?+piai??=(1+pi2?+pi4?+?+piai?1??)+(pi?+pi3?+pi5?+?+piai??)=(1+p)(1+pi2?+pi4?+?+piai?1??)??

顯然這兩個括號內都是偶數項，則有：

( 1 + p ) ( 1 + p i 2 + p i 4 + ? + p i a i ? 1 ) = ( 1 + p ) ( 1 + p i 4 + p i 8 ? + p i a i ? 3 ) + ( p i 2 + p i 6 + p i 10 + ? + p i a i ? 1 ) = ( 1 + p ) ( 1 + p 2 ) ( 1 + p i 4 + p i 8 ? + p i a i ? 3 ) \begin{aligned}&\ \ \ \ \ (1+p)(1+p_i^2+p_i^4+\cdots+p_i^{a_{i-1}})&\\&=(1+p)(1+p_i^4+p_i^8\cdots+p_i^{a_{i-3}})+(p_i^2+p_i^6+p_i^{10}+\cdots+p_i^{a_i-1})&\\&=(1+p)(1+p^2)(1+p_i^4+p_i^8\cdots+p_i^{a_{i-3}})\end{aligned} ? (1+p)(1+pi2?+pi4?+?+piai?1??)=(1+p)(1+pi4?+pi8??+piai?3??)+(pi2?+pi6?+pi10?+?+piai??1?)=(1+p)(1+p2)(1+pi4?+pi8??+piai?3??)??

若 ( 1 + p ) (1+p) (1+p) 和 ( 1 + p 2 ) (1+p^2) (1+p2) 均為 2 2 2 的冪，顯然有 ( 1 + p ) < ( 1 + p 2 ) ? ( 1 + p ) ∣ ( 1 + p 2 ) (1+p)<(1+p^2)\Rightarrow(1+p)\mid (1+p^2) (1+p)<(1+p2)?(1+p)∣(1+p2)

( 1 + p 2 ) = ( p 2 ? 1 ) + 2 = ( p + 1 ) ( p ? 1 ) + 2 (1+p^2)=(p^2-1)+2=(p+1)(p-1)+2 (1+p2)=(p2?1)+2=(p+1)(p?1)+2

若 ( 1 + p ) ∣ ( 1 + p 2 ) (1+p)\mid (1+p^2) (1+p)∣(1+p2)，則 ( 1 + p ) ∣ ( p ? 1 ) , ( 1 + p ) ∣ 2 ? p = 1 (1+p)\mid (p-1),(1+p)\mid 2\Rightarrow p=1 (1+p)∣(p?1),(1+p)∣2?p=1

1 1 1 顯然不是質數，顯然 ( 1 + p ) (1+p) (1+p) 和 ( 1 + p 2 ) (1+p^2) (1+p2) 不可能為 2 2 2 的冪，因此 ? i , a i = 1 \forall i,a_i=1 ?i,ai?=1，

因此所有合法的 N N N，一定是若干 p p p 的一次方的乘積，且 ( 1 + p ) (1+p) (1+p) 是 2 2 2 的冪， p < 2 31 p<2^{31} p<231，合法的 p p p 顯然非常少，只有 8 8 8 個，我們可以直接暴力 O ( log ? p ) O(\log p) O(logp) 找到這 8 8 8 個數，

問題就變成了，給定 n n n 個數 q i q_i qi?，求從這 n n n 個數中選出若干個數，乘積 N N N 僅有這 8 8 8 個 p p p 組成，且不能有重復，如何選取 q i q_i qi? 使得它們的約數和 M M M 最大，

我們可以預處理出所有可能的 N N N ，對于每個輸入的 q i q_i qi?，使用二進制數表示它包含這 8 8 8 個數里的那幾個，這樣 & 起來為 0 0 0 說明沒有重復，我們就可以直接進行狀壓DP， f [ i ] f[i] f[i] 表示 i i i 能否在合法的前提下被湊出來，時間復雜度 O ( 2 8 × n ) O(2^8\times n) O(28×n)，

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e3 + 7, maxp = 10 + 7;
int n, m, s, t, k, ans;
int p[maxp], pow_num[maxp], tot;
int q[maxn];
int f[maxn];

void init()
{
	ll x = 4;
	int cnt = 2; 
	while (x < (1ll << 31) + 1) {
		ll y = x - 1; 
		bool flag = 1;
		for (ll i = 2; i * i <= y; ++ i) {
			if (y % i == 0) {
				flag = 0;
				break;
			}
		}
		if(flag) p[tot] = y, pow_num[tot ++ ] = cnt;
		x <<= 1; 
		cnt ++ ;
	} 
}

int check(int x)
{
	int cnt = 0;
	for (int i = 0; i < tot; ++ i) {
		if(x % p[i] == 0) {
			cnt |= (1 << i);
			x /= p[i];
		} 
	} 
	if(x > 1) return 0;
	return cnt;
}

int cal(int x)
{
	int res = 0;
	for (int i = 0; i < tot; ++ i) {
		if(x & (1 << i))
			res += pow_num[i];
	}
	return res;
}

int main()
{
	init();	
	while(scanf("%d", &n) != EOF) {
		memset(f, 0, sizeof f);
		for (int i = 1; i <= n; ++ i) {
			int x;
			scanf("%d", &x);
			q[i] = check(x); 
			if(q[i] == 0)
				i -- , n -- ;
		}	
		if(n == 0) {
			puts("NO");
			continue;
		}		
		f[0] = 1;
		int ans = 0;
		for (int i = 1; i <= n; ++ i) 
			for (int j = 0; j < (1 << tot); ++ j) 
				if((j & q[i]) == 0) //沒有重復
					f[j | q[i]] |= f[j];
		for (int i = 0; i < (1 << tot); ++ i)
			if(f[i])
				ans = max(ans, cal(i));
		cout << ans << endl;
	}
	return 0;
}

其中題目中的素數 p p p 實際上就是梅森素數：
在這里插入圖片描述

1.5.8 中國剩余定理

Problem A.Voyager 1（Java高精，中國剩余定理）

ZOJ 3341

給定兩個整數 A ? 1 A_{-1} A?1? 和 A 0 A_0 A0?，以及一個長度為 L L L 的操作串 O p Op Op（僅包括加減乘），對于 1 ≤ i ≤ L , A i = A i ? 2 O p i A i ? 1 1\le i\le L,A_i=A_{i-2}\ Op_i\ A_{i-1} 1≤i≤L,Ai?=Ai?2? Opi? Ai?1?（對 A i ? 2 A_{i-2} Ai?2? 和 A i ? 1 A_{i-1} Ai?1? 進行 O p + i Op+i Op+i 操作），求 A L A_L AL?，

所有操作均在模 M M M 的意義下進行，其中 M M M 為小于 1000 1000 1000 的所有質數的乘積，

1 ≤ L ≤ 3 × 1 0 5 1\le L\le 3\times 10^5 1≤L≤3×105

Solution

顯然 M M M 是一個非常非常大的數， 1000 ! 1000! 1000! 級別的數，直接進行高精度計算顯然會爆炸超時，

但是給定的 M M M 為小于 1000 1000 1000 的所有質數的乘積，顯然我們可以分別求出在模這些質數下的結果，然后中國剩余定理合并即可…

資料還是很大，需要使用大數…所以Java yyds

Code

1.6 分析

Problem A.Bridge

ZOJ 2614

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/337749.html

標籤：其他

上一篇：集合全套以及知識點整合

下一篇：【LeetCode系列】楊輝三角

紅書《題目與解讀》第一章 數學 題解《ACM國際大學生程式設計競賽題目與解讀》

紅書《題目與解讀》第一章 數學 題解《ACM國際大學生程式設計競賽題目與解讀》

目錄

第一章 數學

1.1 概率

Problem A.Coupons （幾何概型，概率）

Problem B.Generator （KMP，期望，高斯消元）

Problem C.Dinner with Schwarzenegger!!! （概率）

1.2 代數

1.2.1 Polya

Problem A.Arif in Dhaka （Polya，等價類計數）

1.2.2 矩陣

Problem A.Tower

Problem B.XX Language

1.2.3 線性方程組

Problem A. Ars Longa

1.2.4 線性規劃

Problem A.Expensive Dirnk

1.3 組合

1.3.1 基本排列組合

The Unreal TournamentUVA 10207

1.3.2 容斥原理

1.3.3 生成函式

1.3.4 生成樹計數

1.3.5 綜合

1.4 博弈

Problem A. Battle for the Ring（SG函式）

Problem B. Fool’s Game

Problem C. Points Game

1.5 數論

1.5.1 模線性方程

Problem A.Integer Sequences （多變元線性同余方程）

1.5.2 歐幾里得

Problem A.Wizards

1.5.3 歐拉定理

Problem A.Strange Limit（拓展歐拉定理）

1.5.4 歐拉函式

Problem A.GCD Determinant（ gcd ? \gcd gcd 矩陣定理）

1.5.5 平方剩余

Problem A.Square Root（二次剩余）

1.5.6 原根

Problem A.Fermat’s Last Theorem

1.5.7 整除與剩余

Problem A.Brute-Force Algorithm（乘法換加法，矩陣快速冪）

Problem B. Interal Roots（多項式，整數）

Problem C.Vivian’s Problem（梅森素數，狀壓DP）

1.5.8 中國剩余定理

Problem A.Voyager 1（Java高精，中國剩余定理）

1.6 分析

Problem A.Bridge

紅書《題目與解讀》第一章數學題解《ACM國際大學生程式設計競賽題目與解讀》

紅書《題目與解讀》第一章數學題解《ACM國際大學生程式設計競賽題目與解讀》

第一章數學