數論

模運算

• $amodb=a??a/b?\times b$

• $nmodp$得到的結果的正負至于被除數$n$有關

模運算的性質：

$(a+b)modm=((amodm)+(bmodm))modm$

$(a?b)modm=((amodm)?(bmodm))modm$ = $((amodm)?(bmodm)+m)modm$

$(a\times b)modm=((amodm)\times (bmodm))modm$

但是除法例外，除法的取模需要用到逆元。

計算減法的時候，通常需要加上模數，防止出現負數。

快速冪

快速求解$a^{b}modp$，可以采用二進制拼湊的思想

對于$b$，它可以看成一個二進制數，可以寫成$2$的冪相加的形式，那么$a^b$可以寫成$a^{(2^i+2^j+...+2^k)}=a^{2^i}\times a^{2^j}\times ...\times a^{2^k}(i,j,k\in S,其中集合S為b轉換成二進制后位置上是1的位置)$

我們只需計算的同時預處理每一項$a^{2^i}$即可

using ll = long long;
ll qmi(ll a, ll b, ll c){ll res = 1;while(b){if(b & 1 == 1) res = res * a % c;a = a * a % c;b >>= 1;}return res;
}

乘法逆元

若$a\times x\equiv 1(modb)$，且$a$與$b$互質，我們定義$x$為$a$的逆元，記為$a^{?1}$,$x$可稱為$a$在模$b$意義下的倒數

對于$\frac{a}{b}modp$，我們可以求出$b$在$modp$意義下的逆元，然后乘上$a$，再$modp$即可

注意對于數$a$在模$p$意義下的乘法逆元，我們需要確保$a$與$p$互質，此時才有$a$的乘法逆元$a^{?1}$，此條件等價于$p$是質數

費馬小定理

$a^{p?1}\equiv 1(modp)$，其中$p$是素數

費馬小定理求逆元
$a\times a^{p?2}\equiv 1(modp)$，根據乘法逆元的定義可知，此時$a$的逆元是$a^{p?2}$

ll inv(ll a, ll p){return qmi(a, p - 2, p);
}

擴展歐幾里得求逆元

根據逆元的定義$ax\equiv 1(modp)$，我們得到方程：$ax?1=yp$（$ax?1$ 是$p$的倍數），則$ax+py=1$

解方程得$xmodp$得到的就是$a$的乘法逆元，同時逆元存在的條件是$gcd(a,p)=1$

求階乘的乘法逆元

同余

兩個整數$a$和$b$對用一個正整數$m$取模后余數相同，則稱$a$和$b$對模$m$同余，記作$a\equiv b(modm)$，這意味著$m|(a?b)$

同余的性質：

• 自反性：$a\equiv a(modm)$
• 對稱性：若$a\equiv b(modm)$，則$b\equiv a(modm)$
• 傳遞性：若$a\equiv b(modm),b\equiv c(modm)$，則$a\equiv c(modm)$
• 同加性：若$a\equiv b(modm)$，則$a\pm c\equiv b\pm c(modm)$
• 同乘性：若$a\equiv b(modm)$，則$a\times c\equiv b\times c(modm)$，若$a\equiv b(modm),c\equiv d(modm)$，則$a\times c\equiv b\times d(modm)$
• 同冪性：若$a\equiv b(modm)$，則$a^c\equiv b^c(modm)$
• 不滿足同除性，但是有，若$ca\equiv cb(modm)$，則$a\equiv b(mod\frac{m}{gcd(m,c)})$

擴展歐幾里得定理

對于給定的兩個整數$a$，$b$，必須存在整數$x$與$y$，使得$a\times x+b\times y=gcd(a,b)$

裴蜀定理

方程$a\times x+b\times y=c$有整數解的充分必要條件是$c$是$gcd(a,b)$的倍數

證明：

• 必要性：令$p=gcd(a,b)$，則有$a=p\times a^{\prime }$，$b=p\times b^{\prime }$；則$c=p\times (a^{\prime }x+b^{\prime }y)$，即$gcd(a,b)$的倍數。

• 充分性：考慮$gcd$的歐幾里得算法。$a,b$通過$b,a\%b$的方式一直輾轉下去，最后會出現$p,0$的形式。原因是$0\le a\%b\le b?1$。對于遞歸出口$p,0$，方程$a\times p+0\times y=c$是否存在解呢？顯然有解，由于充分性，這里$a$取$\frac{c}{p}$即可。那么輾轉相除過程中，下面的成立能否推得上面的成立呢？

  • 對于方程$b{x}_1+a\%b\times y_1=c=ax+by$

  • $左邊=b{x}_1+(a??\frac{a}{b}?\times b)\times y_1=a{y}_1+b{x}_1??\frac{a}{b}?\times b{y}_1=a{y}_1+b\times (x_1??\frac{a}{b}?\times y_1)=右邊=ax+by$

    所以找到一組特解：$x=y_1$，$y=x_1??\frac{a}{b}?\times y_1$，就可以通過最下面的特解推得所有的特解。

  • 對于特解$(x_0,y_0)$，設下一組解是$(x_0+d_1,y_0+d_2)$

    有$a\times (x_0+d_1)+b\times (y_0+d_2)=c$，又，$a\times x_0+b\times y_0=c$，則$a{d}_1+b{d}_2=0$

    故，$\frac{d_1}{d_2}=?\frac{b}{a}=?\frac{b/gcd(a,b)}{a/gcd(a,b)}$

    則$d_1=\frac{b}{gcd(a,b)}$，$d_2=?\frac{a}{gcd(a,b)}$，故一般解為：

    $x=x_0+k\times \frac{b}{gcd(a,b)}$，$y=y_0?k\times \frac{a}{gcd(a,b)}(k\in Z)$

  • 若要求$x$的最小整數解，則可以通過$(x_{0}mod(\frac{b}{gcd(a,b)})+\frac{b}{gcd(a,b)})mod{x}_0$，原因是$x_0$的周期是$\frac{b}{gcd(a,b)}$，所以可通過取模的方式得到結果

擴展歐幾里得算法

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

GCD

最大公約數：歐幾里得算法，時間復雜度$O(loga)$

$gcd(a,b)=gcd(b,amodb)$

證明如下：

• 令$p=gcd(a,b)$，則有$a=p\times a^{\prime }$，$b=p\times b^{\prime }$，$gcd(a^{\prime },b^{\prime })=1$

  • $amodb=a??a/b?\times b=p\times a^{\prime }?p\times b^{\prime }\times ?a/b?$

  • 可以看出，$p|b$， $p|(amodb)$

• 那么$p$是否是最大公約數呢？即我們需要證明$gcd(b^{\prime },a^{\prime }?b^{\prime }\times ?a/b?)=1$

  • 令$gcd(b^{\prime },a^{\prime }?b^{\prime }\times ?a/b?)=d$，則有$b^{\prime }=d\times b^{\prime \prime }$，$a^{\prime }?b^{\prime }\times ?a/b?=d\times c$
  • 轉換得到$a^{\prime }=d\times c+b^{\prime }\times ?a/b?=d\times c+d\times b^{\prime \prime }\times ?a/b?$
  • 可以發現$d|b^{\prime }$， $d|a^{\prime }$，與上述$gcd(a^{\prime },b^{\prime })=1$矛盾，則命題得證。

歐拉函數

$\mathrm{1...}N$中與$N$互質的數的個數，被稱為歐拉函數，記作$?(N)$

在唯一分解定理中，$N=p_1^{a_1}\times p_2^{a_2}\times ...\times p_m^{a_m}$，則$?(N)=N\times \frac{p_1?1}{p_1}\times \frac{p_2?1}{p_2}\times ...\times \frac{p_m?1}{p_m}=N\times (1?\frac{1}{p_1})\times (1?\frac{1}{p_2})\times ...\times (1?\frac{1}{p_m})$

證明：

先對$N$分解質因數，得到$N=p_1^{a_1}\times p_2^{a_2}\times ...\times p_m^{a_m}$

在$[1,N]$中，我們先將所以$p_1,p_2,...,p_m$的倍數減掉，再將所有$p_i\times p_j$的倍數的數加上，再減去$p_i\times p_j\times p_k$的倍數的數，以此類推。最后剩下的就是與$N$互質的數的個數。式子表達為$N?(\frac{N}{p_1}+\frac{N}{p_2}+...+\frac{N}{p_m})+(\frac{N}{p_1{p}_2}+\frac{N}{p_1{p}_3}+...)?(\frac{N}{p_1{p}_2{p}_3}+...)...$

該式就是$N\times (1?\frac{1}{p_1})\times (1?\frac{1}{p_2})\times ...\times (1?\frac{1}{p_m})$的展開式

公式法求歐拉函數

#include <bits/stdc++.h>
using namespace std;void solve() {int n;cin >> n;auto f = [&](int x) -> int {int res = x;for (int i = 2; i <= x / i; i ++) {if (x % i != 0) continue;res = res / i * (i - 1);while (x % i == 0) x /= i;}  if (x > 1) res = res / x * (x - 1); return res;};cout << f(n) << endl;
}int main() {int t;cin >> t;while (t --) {solve();}return 0;
}

篩法求歐拉函數

對于一個質數$p$來說，$?(p)=p?1$

對于每一個數$primes[j]\times i$來說

• 當$i\%primes[j]=0$時，$i$中的質因子包括$primes[j]$，則有$?(primes[j]\times i)=?(i)\times primes[j]$
• 當$i\%primes[j]\ne 0$時，$i\times primes[j]$中的質因子既包括$i$中的質因子，又包括$primes[j]$，則有$?(primes[j]\times i)=?(i)\times primes[j]\times (1?\frac{1}{primes[j]})$

#include <bits/stdc++.h>s
using namespace std;#define int long longconst int N = 1000010;
int cnt, primes[N];
bool st[N];
int phi[N];int getEuler(int n) {phi[1] = 1;for (int i = 2; i <= n; i ++) {if (st[i] == false) {primes[cnt ++] = i;phi[i] = i - 1;}for (int j = 0; j < cnt && primes[j] <= n / i; j ++) {st[primes[j] * i] = true;if (i % primes[j] == 0) {phi[i * primes[j]] = phi[i] * primes[j];break;}phi[i * primes[j]] = phi[i] * primes[j] / primes[j] * (primes[j] - 1);}}int res = 0;for (int i = 1; i <= n; i ++) {res += phi[i];}return res;
}signed main() {int n;cin >> n;cout << getEuler(n) << endl;return 0;
}

質數

分解質因數

給定一個數$x$，由唯一分解定理可知，$x=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}...(p_1<p_2<p_3)$，我們從小到大枚舉每一個數，最先整除$x$的除數$n$一定是素數。同時將這個數中所有$n$的因子除干凈，那么下次$x$被整除時除數也是素數，從而分解了質因數。

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;for (int i = 0; i < n; i ++) {int x;cin >> x;map<int, int> cnt;vector<int> res;for (int j = 2; j <= x / j; j ++) {if (x % j != 0) continue;res.push_back(j);while (x % j == 0) {cnt[j] ++;x /= j;}}if (x > 1) {res.push_back(x);cnt[x] ++;}for (auto& u : res) {cout << u << " " << cnt[u] << endl;}cout << endl;}return 0;
}

普通篩法

給定一個整數$x$，并篩掉所有倍數，如$2x,3x,4x...$

篩完后，$vis[i]=false$的為素數

這種方法的時間復雜度是$O(nlogn)$級別

對于每一個外層循環變量$i$，內層循環枚舉所有不超過$n$的$i$的倍數，枚舉次數是$?\frac{n}{i}?$，又$?\frac{n}{i}?<\frac{n}{i}$，有調和級數的漸近公式${\sum }_{i=1}^n\frac{1}{i}\approx ln(n+1)+0.577218$，其中$0.577218$是歐拉常數

所以復雜度是$O(nlogn)$級別

雖然這個篩法的時間復雜度很差，但是調和級數枚舉引人深思，這種枚舉方式非常巧妙，而且復雜度僅有$O(logn)$級別

埃式篩法

在調和級數枚舉的篩法中，我們發現枚舉4的倍數無意義，因為從這里篩掉的數一定從2的倍數里篩掉了，所以我們想到：只用質數去篩

其復雜度只有$O(nloglogn)$

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int cnt, primes[N], n;
bool st[N];int main() {cin >> n;for (int i = 2; i <= n; i ++) {if (st[i]) continue;primes[cnt ++] = i;for (int j = 2 * i; j <= n; j += i) {st[j] = true;}}cout << cnt << endl;return 0;
}

歐拉篩

通過對埃氏篩法的分析，我們發現$6=2\times 3$會被質數$2$和$3$各篩一次。一個數有多少個質因子，它就會被篩多少次。那么我們能否讓一個數只被篩掉一次呢？

歐拉篩法可以做到并且每個數會被它的最小質因子篩掉

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int cnt, primes[N], n;
bool st[N];int main() {cin >> n;for (int i = 2; i <= n; i ++) {if (!st[i]) primes[cnt ++] = i; //是素數for (int j = 0; j < cnt && primes[j] <= n / i; j ++) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}

• 設$x=i\times primes[j]$
• 若$imodprimes[j]\ne 0$，則$i$中沒有$primes[j]$這個質因子。又因為$j$是從小到大遍歷的，所以$primes[j]<i$，則$primes[j]$是$x$的最小質因子
• 若$imodprimes[j]=0$ ，說明$primes[j]$是$i$的一個質因子。又因為$j$是從小到大遍歷的，所以$primes[j]$是$i$的最小質因子。所以$primes[j]$是$x$的最小質因子
• 綜上所述，每個數都是被其最小質因子$primes[j]$篩掉且只會被篩掉一次

調和級數枚舉模型

內容參考于：[OI&ACM]調和級數枚舉倍數模型 - 知乎
給定一個數$n(n\le 10^6)$，求$[1,n]$中所有整數$i$的正因子個數

思路：枚舉$[1,n]$中的所有數$i$，對$i$的所有倍數，$i$ 會增加$1$的貢獻。考慮調和級數枚舉：

int d[1000001] = {0}; // 儲存因數倍數，初始全為 0
for (int i = 1; i <= n; i++) // 枚舉 [1, n] 的數
{for (int j = i; j <= n; j += i) // 枚舉 i 的倍數{d[j]++;}
}

時間復雜度為$O(nlogn)$級別

下面的題目都應用了該模型，讀者不妨觀看思考

題目1：Problem - D - Codeforces

大意：給定一個長度為$n(n\le 10^5)$的數組，每次操作可以任取一些位置上的數，并將該位置上的數染成黑色。然后將這些被染成黑色的位置索引的所有倍數染成綠色，每次操作的得分是該數組中黑色和綠色位置上的數的最大值。由于選擇染成黑色的操作有$2^n?1$種，所以我們要求出所有操作的得分的和

選擇每個數所能得到的最大值是容易處理的。

vector<int> maxv(n + 1, 0);
for (int i = 1; i <= n; i ++) {for (int j = i; j <= n; j += i) {maxv[i] = max(maxv[i], a[j]);}
}

我們明確$maxv$數組的含義：選擇第$i$上的數，將其涂成黑色，并將其索引的倍數涂成綠色，所能得到的最大值。假設有這樣的$maxv$數組，$maxv=[1,6,7,3]$，$1$貢獻了$1$次，$3$貢獻了$2$次，$6$貢獻了$4$次，$7$貢獻了$8$次。這是因為：對于第一個位置上的數，我們有如下的選擇方式$[1],[1,2],[1,3],[1,4],[1,2,3],[1,2,4],[1,3,4],[1,2,3,4]([1,3,4]表示我們選擇第1，3，4個數字，其余同理)$，由于$1$是最小的，在如下選擇中只貢獻了$1$次，就是選擇方式為$[1]$的時候。所以我們可以將$maxv$數組排序并用貢獻法求出答案

sort(maxv.begin() + 1, maxv.begin() + n + 1);
LL res = 0, pow2 = 1;	
for (int i = 1; i <= n; i ++) {res = (res % mod + maxv[i] * pow2 % mod) % mod;pow2 = pow2 * 2 % mod;
}cout << res << endl;

題目2：Problem - D - Codeforces

大意：給定一個數組$a$，其長度為$n$，其中$1\le n\le 10^6$，$1\le a_i\le n$。若不存在$k，(1\le k\le n)$使得$a_k|a_i$，$a_k|a_j$，那么稱$(i,j)$是對兒好整數。求好整數的數量。

• 條件$a_k|a_i$，$a_k|a_i$可以轉化為$a_k|gcd(a_i,a_j)$。由于值域僅有$10^6$級別，我們可以預處理出$f(x)(1\le x\le 10^6)$，$f(x)$表示$gcd(i,j)=x$好整數的個數。

  • 令$y|gcd(a_i,a_j)$，此時$a_i$，$a_j$是$y$的倍數，故可以枚舉$y$的倍數計算出數量$sum$。那么$y|gcd(a_i,a_j)$中$(i,j)$的對數是$C_{sum}^2=\frac{sum\times (sum?1)}{2}$。其中存在兩種情況$y=gcd(a_i,a_j)$或$y<gcd(a_i,a_j)$，（也就是$gcd(a_i,a_j)$是$y$的大于$1$倍的倍數）。所以$f(x)=\frac{sum\times (sum?1)}{2}?f(2x)?f(3x)?...$

  for (int i = n; i >= 1; i --) {int s = 0, t = 0;for (int j = i; j <= n; j += i) {s += cnt[j];t += f[j];}f[i] = s * (s - 1) / 2 - t;}
  

• 在值域之中，我們將$a_m(1\le m\le n)$及其倍數篩掉，剩下的就是$f(x)$中$x$可以取的值。于是$ans={\sum }_{i=1}^{n}f(i)(其中i未被篩掉)$

#include <bits/stdc++.h>
using namespace std;using LL = long long;#define int LLvoid solve() {int n;cin >> n;vector<int> f(n + 1, 0);vector<int> cnt(n + 1, 0);for (int i = 0; i < n; i ++) {int x;cin >> x;cnt[x] ++;}for (int i = n; i >= 1; i --) {int s = 0, t = 0;for (int j = i; j <= n; j += i) {s += cnt[j];t += f[j];}f[i] = s * (s - 1) / 2 - t;}vector<int> vis(n + 1, false);for (int i = 1; i <= n; i ++) {if (cnt[i]) {for (int j = i; j <= n; j += i) {vis[j] = true;}}}int res = 0;for (int i = 1; i <= n; i ++) {if (vis[i] == false) {res += f[i];}}cout << res << endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t --) {solve();}return 0;
}

約數

約數個數

對于一個正整數$x$，由于唯一分解定理，$x=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times p_4^{a_4}...$

對于$x$的每一個約數$y$，$y$都能寫成$y=p_1^{b_1}\times p_2^{b_2}\times p_3^{b_3}\times p_4^{b_4}...(0\le b_1\le a_1,0\le b_2\le a_2,0\le b_3\le a_3,0\le b_4\le a_4)$

所以約數個數為$(a_1+1)\times (a_2+1)\times (a_3+1)\times (a_4+1)\times ...$

約數之和

約數之和$sum=(p_1^0+p_1^1+...+p_1^{a_1})\times (p_2^0+p_2^1+...+p_2^{a_2})\times (p_3^0+p_3^1+...+p_3^{a_3})\times (p_4^0+p_4^1+...+p_4^{a_4})\times ...$

由分配律將上述括號拆開可得：$x_1+x_2+x_3+...+$，其中每一項都是$x$的約數

#include <bits/stdc++.h>
using namespace std;using LL = long long;const int mod = 1e9 + 7;int n;
map<int, int> cnt;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 0; i < n; i ++) {int x;cin >> x;for (int j = 2; j <= x / j; j ++) {if (x % j != 0) continue;int t = 0;while (x % j == 0) {t ++;x /= j;}cnt[j] += t;}if (x > 1) cnt[x] ++;}   LL res = 1;for (auto& [u, v] : cnt) {LL t = 0;for (int j = 0; j <= v; j ++) {t = (t * u % mod + 1) % mod;}res = res * t % mod;}cout << res << endl;return 0;
}

組合數

$C_n^m=C_{n?1}^{m?1}+C_{n?1}^m$

可由此式子遞推計算組合數

void init() {for (int i = 0; i <= N - 1; i ++) {c[i][0] = 1;}for (int i = 1; i <= N - 1; i ++) {for (int j = 1; j <= N - 1; j ++) {c[i][j] = (c[i - 1][j] % mod + c[i - 1][j - 1] % mod) % mod;}}
}

$C_n^m=\frac{A_n^m}{A_m^m}=\frac{\frac{n!}{(n?m)!}}{m!}=\frac{n!}{m!(n?m)!}$

可以預處理出來$fact[N]$與$infact[N]$

故$C_n^m=fact[N]\times infact[m]\times infact[n?m]$

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"
typedef pair<int, int> pII;
const int p = 1e9 + 7;
const int N = 100010;
LL fact[N], infact[N];LL qmi(LL a, LL b, LL p) {LL res = 1;while (b) {if (b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;
}LL inv(LL x) {return qmi(x, p - 2, p);}void init(int n) {fact[0] = 1;for (int i = 1; i <= n; i ++) fact[i] = fact[i - 1] * i % p;infact[n] = inv(fact[n]);for (int i = n - 1; i >= 0; i --) infact[i] = infact[i + 1] * (i + 1) % p;
}void solve() {int n, m; cin >> n >> m;cout << (fact[n] % p) * (infact[n - m] % p * infact[m] % p) % p << endl;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init(100005);int t; cin >> t;while (t --) {solve();}return 0;
}

盧卡斯定理

$C_n^m=C_{\frac{n}{p}}^{\frac{m}{p}}\times C_{nmodp}^{mmodp}$