質數篩

用于快速處理 1～n 中所有素數的算法

因為依次遍歷判斷每一個數是否質數太慢，所以把一些明顯不能質數的篩出來

普通篩法，對于每個整數，刪除掉其倍數。

bool vis[N];//0表示是質數
int pri[N],o; //質數表
void get(int n) {vis[1] = true; //1不是素數for(int i = 2; i <= n; ++i) {//從2開始if(!vis[i])pri[++o] = i; //加入質數表for(int j = 2 * i; j <= n; j += i)vis[j] = 1;//刪除到n的整數倍}
}

線性篩和埃氏篩-CSDN博客

埃氏篩

在普通篩法的過程中，發現篩 4 的倍數毫無意義，因為 4 的倍數肯定已被 2 的倍數篩過了，所以優化方法是只用質數去篩。

?對于每一個整數，只有他是質數時才去篩

if(!vis[i]){
? ? ? ? ? ? primes[ ++ tot] = i;?
? ? ? ? ? ? for(int j = 2 * i; j <= n; j += i)
? ? ? ? ? ? ? ? vis[j] = 1;//進入if里了
? ? ? ? }

線性篩（歐拉

讓每個數都被其最小的質因數篩掉，故一個數只被篩一次，復雜度為O(n)

實現就是，對于每個數，我們都將他對整個現在已有的質數表篩一遍，比如3是質數，那么把已有的2相乘，篩掉6，但是并不往下進行，因為比如12，最小質數因數是3，在遍歷到4時自然而然就篩掉了，這樣每個數就只會被他最小質因數篩掉一次，達到了線性

for(int i = 2; i <= n; ++i) {if(!vis[i]) //是素數pri[ ++ o] = i;for(int j=1;j<o;j++)if(i*pri[j]<=n)vis[i*pri[j]]=1;else break;//}
}

快速冪：

1. 基本概念

一個在O(logn)的時間內計算an的魔術技巧小技巧，而暴力的計算需要O(n)的時間，基本思想就是將指數按照二進制表示來分割。例如

ll ksm(ll a,ll b,ll p){ll ans=1;while(b){if(b&1) ans=ans*a%p;//b & 1：用按位與運算判斷 b 的二進制最低位是否為 1（比如 b=5 是 101，b&1 結果為 1；b=4 是 100，b&1 結果為 0 ）。
如果最低位是 1，說明當前這一位對應的冪次需要乘到結果里。
ans = ans * a % p：把當前的 a（對應某一 “二進制位權” 的冪）乘到結果 ans 中，再對 p 取模，保證數值不會溢出，且符合題目對結果取模的要求。a=a*a%p;//每次循環，底數 a 自乘一次（即 a = a2 % p ），對應指數二進制位的位權翻倍。
比如初始 a=3（對應 3 1），第一次自乘后 a=32=9（對應 3 2 ），第二次自乘后 a=92=81（對應 3 4），第三次自乘后 a=812=6561（對應 3 8 ）…… 以此類推，剛好匹配指數二進制各位的權值b>>=1;//后移}return ans;
}

• a：底數，即要做冪運算的基數。
• b：指數，即冪次。
• p：模數，計算結果要對?p?取模，避免數值過大溢出或滿足題目對結果范圍的要求。

?

2. 矩陣快速冪

矩陣快速冪 = 矩陣乘法 + 快速冪。

單位矩陣是對角線全為 1，其他位置均為 0 的矩陣，記為 I，性質：A×I=A。

include <iostream>
#include <cstring>
using namespace std;typedef long long LL;         // 使用LL作為long long的別名，簡化代碼
const int MOD = 1e9 + 7;      // 定義模數，防止整數溢出
const int N = 105;            // 定義矩陣的最大尺寸int n;                        // 矩陣的實際大小
LL k;                         // 矩陣需要乘方的次數// 矩陣結構體，封裝矩陣乘法和單位矩陣設置操作
struct Matrix {LL a[N][N];               // 存儲矩陣元素// 默認構造函數，初始化矩陣為全0Matrix() {memset(a, 0, sizeof a);}// 重載乘法運算符，實現矩陣乘法Matrix operator*(const Matrix& b) const {Matrix c;// 三層循環實現矩陣乘法，注意取模防止溢出for (int i = 1; i <= n; i++)for (int k = 1; k <= n; k++)for (int j = 1; j <= n; j++)c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % MOD;return c;}// 設置當前矩陣為單位矩陣（對角線為1，其余為0）void setIdentity() {for (int i = 1; i <= n; i++) a[i][i] = 1;}
};int main() {cin >> n >> k;  // 輸入矩陣大小n和冪次k// 讀取原始矩陣Matrix base;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> base.a[i][j];// 初始化結果矩陣為單位矩陣，相當于數值計算中的1Matrix res;res.setIdentity();// 快速冪算法：計算矩陣的k次冪// 原理與數值快速冪相同，但使用矩陣乘法代替數值乘法while (k) {if (k & 1) res = res * base;  // 如果當前位為1，則乘上當前的basebase = base * base;            // base平方k >>= 1;                       // k右移一位，相當于除以2}// 輸出結果矩陣for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++)cout << res.a[i][j] << ' ';cout << endl;}return 0;
}

?

?

??擴展歐幾里得算法

?一、核心目標：求解?ax + by = gcd(a, b)?的整數解

擴展歐幾里得算法本質是?在求最大公約數（gcd）的同時，找到滿足?ax + by = gcd(a, b)?的整數?x?和?y?。
比如：a=5, b=3，gcd 是 1，同時能找到?x=2, y=-3（因為?5×2 + 3×(-3) = 10-9=1 = gcd(5,3)?）。

---

?二、遞歸推導：從?gcd(b, a%b)?反推?gcd(a, b)?的解

歐幾里得算法的核心是?gcd(a, b) = gcd(b, a%b)（比如?gcd(5,3)=gcd(3,2)=gcd(2,1)=gcd(1,0)=1?）。
擴展歐幾里得在此基礎上，遞歸地從?gcd(b, a%b)?的解，反推?gcd(a, b)?的解，

ll exgcd(ll a, ll b, ll &x, ll &y){ // 傳引用修改 x、yif(b == 0){ // 遞歸出口：b=0時，gcd是a，解為x=1, y=0x = 1; y = 0; return a; }// 遞歸求解 gcd(b, a%b)，同時得到子問題的解 (x', y')ll d = exgcd(b, a % b, y, x); // 注意：這里交換了 y、x 的位置！// 子問題的解是 (x', y')，但因為交換了參數，實際拿到的是 y=x', x=y' // 根據推導公式，當前層的 y = x' - (a/b)*y' y -= (a / b) * x; return d; // 返回 gcd(a,b)
}

以?a=5, b=3?為例，逐步看遞歸和求解過程：

1. 第一層調用：exgcd(5, 3, x, y)

   • b≠0，遞歸調用?exgcd(3, 5%3=2, y, x)

2. 第二層調用：exgcd(3, 2, y, x)

   • b≠0，遞歸調用?exgcd(2, 3%2=1, y, x)

3. 第三層調用：exgcd(2, 1, y, x)

   • b≠0，遞歸調用?exgcd(1, 2%1=0, y, x)

4. 第四層調用：exgcd(1, 0, y, x)

   • b=0，觸發遞歸出口：x=1, y=0，返回?d=1（即 gcd=1 ）

5. 返回第三層：

   • 此時?d=1，且因為參數交換，當前層的?y?是子問題的?x=1，x?是子問題的?y=0
   • 執行?y -= (2/1)*x?→?y = 0 - 2*1 = -2
   • 返回?d=1，當前層的解是?x=0, y=-2?不對？別急，繼續看… 其實這里的?x,y?是相對于當前層?a=2, b=1?的，?哦，因為參數交換后，邏輯需要再仔細看：

   實際第三層的調用是?exgcd(2, 1, y, x)，所以子問題（第四層）的?x=1, y=0?會被賦值給?當 前層的?y?和?x?，即：

   • 當前層（第三層）的?y?= 子問題的?x=1
   • 當前層（第三層）的?x?= 子問題的?y=0
     然后執行?y -= (2/1)*x?→?y = 1 - 2*0 = 1
     所以第三層的解是?x=0, y=1，對應等式?2*0 + 1*1 = 1 = gcd(2,1)，正確！

6. 返回第二層：

   • 第二層調用是?exgcd(3, 2, y, x)，子問題（第三層）返回?d=1，且當前層的?y?= 第三層的?x=0，x?= 第三層的?y=1
   • 執行?y -= (3/2)*x?→?3//2=1，所以?y = 0 - 1*1 = -1
   • 此時第二層的解是?x=1, y=-1，對應等式?3*1 + 2*(-1) = 3-2=1 = gcd(3,2)，正確！

7. 返回第一層：

   • 第一層調用是?exgcd(5, 3, x, y)，子問題（第二層）返回?d=1，且當前層的?y?= 第二層的?x=1，x?= 第二層的?y=-1
   • 執行?y -= (5/3)*x?→?5//3=1，所以?y = 1 - 1*(-1) = 2
   • 此時第一層的解是?x=-1, y=2，對應等式?5*(-1) + 3*2 = -5+6=1 = gcd(5,3)，正確！

最終，exgcd(5,3,x,y)?執行后，x=-1, y=2，滿足?5*(-1) + 3*2 = 1?。

?

乘法逆元

1. 基本概念

更準確的來說是模意義下的乘法逆元。單位元：在一個集合中，對于某種運算?，如果對于任何的集合元素 a，和元素 e 運算，得到還是集合元素 a 本身，則稱 e 為這個運算下的單位元。例如加法運算的單位元是 0，乘法的單位元是 1。逆元：在一個集合中，對于某種運算?，如果任意兩個元素的運算結果等于單位元，則稱這兩個元素互為逆元。加法中 a 的逆元是 - a，乘法中 a 的逆元是a1?即a?1。所以，數學上的乘法逆元就是直觀上的倒數，即ax=1，x 即為 a 的逆元。對于模意義下的乘法逆元，即滿足ax≡1(modb)時，則稱 x 為 a 關于模 b 的逆元。

很容易看出來，這是擴展歐幾里得的一種運用?

擴展歐幾里得法

ax≡1(modb)?ax+by=1

?但是利用以上的歐幾里得，我們只能求出最近的一個乘法逆元，比如3m10，得到-3；

此時，應該進行魔術技巧

x = (x % n + n) % n

操作，把不論正負，求取最小正數逆元

費馬小定理法

定義：若 p 為質數，gcd(a,p)=1，則ap?1≡1?(mod p)。

證明：

• 因為ax≡1(modb)
• 所以ax≡ab?1(modb)
• 故x≡ab?2(modb)

然后就可以用快速冪求解，時間復雜度為O(logb)。?

ll inv(ll a,ll p){return ksm(a,p-2,p);//ksm上面呢
}

線性求逆元

求出 1-n 中每個數的逆元。

void getinv(ll n){inv[1] = 1;for(int i = 2; i <= n; ++i){inv[i] = (p - (p / i)) * inv[p % i] % p;}
}

?

線性求逆元的遞推公式

對于任意一個數 i，它的逆元?inv[i]?可以通過如下遞推公式計算得出

inv[i]=(p??p/i?)×inv[p%i]%p

推導：

????????我們令?k=?p/i??以及?r=p%i，那么顯然有?p=k×i+r，也就是?k×i+r≡0(modp)。

????????對這個同余式進行變形，在等式兩邊同時乘以?i?1×r?1，就可以得到?k×r?1+i?1≡0(modp)。

????????進一步移項，就能得到?i?1≡?k×r?1(modp)。

????????為了保證逆元是正數，我們把公式調整為?i?1≡(p?k)×r?1(modp)，這里的 r 其實就是?p%i。

遞推的起始條件
當 i 等于 1 時，它的逆元毫無疑問是 1，即?inv[1]=1，這是整個遞推過程的起點。

?

組合數學?

基本求法

ll res[N][N];//記憶化，避免重復計算
ll C(ll n,ll m){if(m ==0 || n == m) return 1;if(res[n][m])return res[n][m];//調用記憶return res[n][m] = C(n - 1, m) + C(n - 1, m - 1);
}

也可以將記憶化演變成動態規劃

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){ll n, m, p;cin>>n>>m>>p;ll total = n + m;vector<vector<ll>> C(total + 1, vector<ll>(total + 1, 0));        // 預處理組合數for(int i = 0; i <= total; i++){C[i][0] = 1 % p;C[i][i] = 1 % p;for(int j = 1; j < i; j++){C[i][j] = (C[i-1][j] + C[i-1][j-1]) % p;}cout<<C[total][n]<<endl;return 0;
}

ps:面對過大數據空間會炸?

?

Lucas 定理?

ll Lucas(ll n, ll m){if(m == 0) return 1;return Lucas(n / p, m / p) * C(n % p, m % p) % p;
}

?逆元法求組合（利用費馬

由于公式

我們想，能不能直接利用階乘自己取模后相除

但是當需要計算?C(n,m)modp?時，不能直接對分子和分母分別取模后相除，因為模運算的除法不滿足分配律

逆元的作用是將模意義下的除法轉換為乘法

（ps，-1不是次方，是逆元的意思）

ll comb(ll n, ll m, ll p) {//這里n上，m下if (m < 0 || m > n) return 0;// 預處理階乘數組vector<ll> fact(n + 1, 1);for (ll i = 1; i <= n; i++) {fact[i] = fact[i - 1] * i % p;}// 計算逆元：fact[m]^(-1) 和 fact[n-m]^(-1)ll inv_m = mod_pow(fact[m], p - 2, p);ll inv_nm = mod_pow(fact[n - m], p - 2, p);//費馬// 計算組合數return fact[n] * inv_m % p * inv_nm % p;
}

?盧卡斯與逆元結合

include <bits/stdc++.h>
using namespace std;typedef long long ll;// 快速冪計算 a^b % p
ll quick_pow(ll a, ll b, ll p) {ll res = 1;while (b > 0) {if (b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;
}// 計算組合數 C(a, b) % p，其中 a < p，b < p
ll comb(ll a, ll b, ll p) {if (b < 0 || b > a) return 0;if (b == 0 || b == a) return 1;// 預處理階乘和逆元vector<ll> fact(p), inv_fact(p);fact[0] = 1;for (int i = 1; i < p; ++i) {fact[i] = fact[i - 1] * i % p;}inv_fact[p - 1] = quick_pow(fact[p - 1], p - 2, p);for (int i = p - 2; i >= 0; --i) {inv_fact[i] = inv_fact[i + 1] * (i + 1) % p;}return fact[a] * inv_fact[b] % p * inv_fact[a - b] % p;
}// 盧卡斯定理計算 C(n, m) % p
ll lucas(ll n, ll m, ll p) {if (m == 0) return 1;return comb(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int T;cin >> T;while (T--) {ll n, m, p;cin >> n >> m >> p;// 計算 C(n+m, n) % pcout << lucas(n + m, n, p) << '\n';}return 0;
}

卡特蘭數?

?catalan數-CSDN博客

?

排列組合與容斥原理

1. 排列數公式

• 從 n 個元素中選 m 個排列：Anm?=n×(n?1)×?×(n?m+1)=n!/(n?m)!?。

2. 容斥原理基礎

• 兩個集合：∣A∪B∣=∣A∣+∣B∣?∣A∩B∣。
• 三個集合：∣A∪B∪C∣=∣A∣+∣B∣+∣C∣?∣A∩B∣?∣A∩C∣?∣B∩C∣+∣A∩B∩C∣。
• 應用場景：計算不滿足某些條件的元素個數，如求 1~n 中不被 2、3、5 整除的數的個數。

?

快速傅里葉變換（FFT）

1. 核心作用

• 加速多項式乘法，將暴力O(n2)的復雜度優化到O(nlogn)。
• 原理：利用復數單位根的性質，將多項式從系數表示轉為點值表示，相乘后再逆變換回系數表示。

2. 基本步驟

1. 預處理單位根：計算復數域上的 n 次單位根。
2. FFT 正變換（DFT）：將多項式轉換為點值形式。
3. 點值相乘：對應點值相乘得到結果多項式的點值表示。
4. 逆變換（IDFT）：轉換回系數形式

?框架（搞不懂，看不懂，不明白，所以就貼了個碼）

const double PI = acos(-1);
struct Complex {double x, y;Complex(double x=0, double y=0) : x(x), y(y) {}
};
Complex operator+(Complex a, Complex b) { return Complex(a.x+b.x, a.y+b.y); }
Complex operator-(Complex a, Complex b) { return Complex(a.x-b.x, a.y-b.y); }
Complex operator*(Complex a, Complex b) { return Complex(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x); }void fft(Complex *a, int n, int inv) {if (n == 1) return;Complex a1[n/2], a2[n/2];for (int i = 0; i < n; i++) {if (i % 2 == 0) a1[i/2] = a[i];else a2[i/2] = a[i];}fft(a1, n/2, inv); fft(a2, n/2, inv);Complex w(1, 0), wn(cos(2*PI/n), inv*sin(2*PI/n));for (int i = 0; i < n/2; i++) {a[i] = a1[i] + w * a2[i];a[i+n/2] = a1[i] - w * a2[i];w = w * wn;}if (inv == -1) {for (int i = 0; i < n; i++) a[i].x /= n;}
}// 計算多項式乘法c = a * b，a和b的次數分別為n和m
void multiply(ll *a, ll *b, ll *c, int n, int m) {int len = 1;while (len < n + m) len <<= 1;Complex *fa = new Complex[len], *fb = new Complex[len];for (int i = 0; i < n; i++) fa[i] = Complex(a[i], 0);for (int i = n; i < len; i++) fa[i] = Complex(0, 0);for (int i = 0; i < m; i++) fb[i] = Complex(b[i], 0);for (int i = m; i < len; i++) fb[i] = Complex(0, 0);fft(fa, len, 1); fft(fb, len, 1);for (int i = 0; i < len; i++) fa[i] = fa[i] * fb[i];fft(fa, len, -1);for (int i = 0; i < n + m; i++) c[i] = (ll)(fa[i].x + 0.5);delete[] fa; delete[] fb;
}

?

?

?

?

?