浅析数论
目录更好的阅读体验戳此进入
还没写完，春测之后有机会继续写。
裴蜀定理
$ ax + by = \gcd(a, b) \iff a, b \in \mathbb{Z}^* $。特别地对于 $ a, b $ 不全为 $ 0 $ 的情况也成立。
证明略。
int N;
int ans;
int main(){
N = read();
ans = abs(read()), --N;
while(N--)ans = __gcd(ans, abs(read()));
printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
gcd
对于一般的 $ \gcd $ 这里不过多赘述，值得一提的只有：
更相减损术，即：$ \gcd(a, b) = \gcd(b, a - b) $。
更进一步地，有 $ \gcd(a, b) = \gcd(b, a \bmod{b}) $。
exgcd（线性同余方程）
对于整数 $ a, b $，要求 $ ax + by = \gcd(a, b) $。
显然存在 $ bx' + (a \bmod{b})y' = \gcd(b, a \bmod{b}) $。
又 $ \gcd(a, b) = \gcd(b, a \bmod{b}) $。
整理并展开 $ a \bmod b $ 得到 $ ax + by = bx' + (a - \lfloor \dfrac{a}{b} \rfloor \times b)y' $。
则显然有 $ x = y', y = x' - \lfloor \dfrac{a}{b} \rfloor \times y $。
问题规模缩减，不断递归，直到最终 $ \gcd = 0 $，或者说 $ b = 0 $ 则回溯 $ x = 1, y = 0 $ 即可。
考虑更一般的形式，即 $ ax + by = c $，其中 $ \gcd(a, b) \mid c $。
令 $ d = \dfrac{c}{\gcd(a, b)} $，显然整除，则 $ x \leftarrow x \times d, y \leftarrow y \times d $ 即可。
此算法得到的为任意解，考虑如何得到 $ x $ 的最小非负解。
发现方程通解为 $ x + k\dfrac{b}{\gcd(a, b)}, y - k\dfrac{a}{\gcd(a, b)} $，以 $ \dfrac{b}{\gcd(a, b)} $ 为模数对 $ x $ 取模转正后求出对应的 $ y $ 即可找到 $ x $ 的最小非负解。
同时这里我们考虑线性同余方程的表示，即给定 $ a, b $，求解 $ ax \equiv c \pmod{b} $，其中 $ \gcd(a, b) \mid c $，显然我们可以将该式转化为 $ ax + by = c $ 中 $ x $ 的解的形式。
费马小定理
若 $ p $ 为质数且 $ \gcd(a, p) = 1 $，那么 $ a^{p - 1} \equiv 1 \pmod{p} $。
同时存在另一种表示形式，对于任意整数 $ a $，有 $ a^p \equiv a \pmod{p} $。
证明待补。
欧拉函数
定义欧拉函数 $ \varphi(n) $ 表示小于等于 $ n $ 的数中与 $ n $ 互质的数的个数。显然有 $ \varphi(1) = 1 $，以及对于质数 $ p $ 有 $ \varphi(p) = p - 1 $。
欧拉函数为不完全积性函数，即对于 $ a \perp b $，有 $ \varphi(a \times b) = \varphi(a) \times \varphi(b) $。
特别地，对于 $ n $ 为奇数，有 $ \varphi(2n) = \varphi(n) $。
存在 $ n = \sum_{d \mid n} \varphi(d) $，莫反易证。
特别地，对于 $ n = p^k $，有 $ \varphi(n) = p^k - p^{k - 1} $，易证。
存在 $ \varphi(n) = n \times \prod \dfrac{p_i - 1}{p_i} $。
线性筛欧拉函数
欧拉函数为不完全积性函数，即对于 $ a \perp b $，有 $ \varphi(a \times b) = \varphi(a) \times \varphi(b) $。
考虑利用此性质，在线性筛的过程中，对于当前枚举的数 $ i $ 以及枚举的质数 $ p $，若满足 $ i \not\equiv 0 \pmod{p} $ 那么一定满足 $ i \perp p $，则有 $ \varphi(i \times p) = \varphi(i) \times \varphi(p) \(。反之我们考虑欧拉函数的质因数分解求法进行推导，即：\) \varphi(i \times p) = i \times p \times \prod \dfrac{p_i - 1}{p_i} $，且我们知道此种情况下因 $ i $ 是 $ p $ 的倍数，那么 $ i $ 中一定存在质因数 $ p $，也就是说 $ i $ 的质因子种类数与 $ i \times p $ 的是相同的，于是可以转化为 $ \varphi(i \times p) = p \times \varphi(i) $。
例题 #1 LG-P2158 [SDOI2008] 仪仗队
题面不太好描述，可以去看原题面，也可以直接看转化，还是比较好理解的。
不难发现答案转化为求所有横纵坐标在 $ [1, n - 1] $ 且互质的点的个数加 $ 2 $，可感性转化为 $ \sum_{i = 1}^{n - 1} \varphi(i) \times 2 - 1 + 2 $，即对称讨论后减去主对角线上重复计算的。我们令 $ n \leftarrow n - 1 $，尝试通过交换求和严谨推导：
\[\begin{aligned} &\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1] \\ =&\sum_{i = 1}^n \sum_{j = 1}^i [\gcd(i, j) = 1] + \sum_{i = 1}^n \sum_{j = i}^n [\gcd(i, j) = 1] - \sum_{i = 1}^n[\gcd(i, i) = 1] \\ =&\sum_{i = 1}^n \sum_{j = 1}^i [\gcd(i, j) = 1] + \sum_{j = 1}^n \sum_{j = 1}^i [\gcd(i, j) = 1] - \sum_{i = 1}^n[\gcd(i, i) = 1] \\ =&\sum_{i = 1}^{n} \varphi(i) \times 2 - 1 \end{aligned} \]线性筛欧拉函数即可。
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define LIM (41000)
template < typename T = int >
inline T read(void);
int N;
int phi[LIM + 100];
int ans(0);
basic_string < int > Prime;
bitset < LIM + 100 > notPrime;
int main(){phi[1] = 1;
for(int i = 2; i <= LIM; ++i){
if(!notPrime[i])Prime += i, phi[i] = i - 1;
for(auto p : Prime){
if(i * p > LIM)break;
phi[i * p] = i % p ? phi[i] * phi[p] : p * phi[i];
notPrime[i * p] = true;
if(i % p == 0)break;
}
}N = read();
if(N == 1)printf("0\n"), exit(0);
for(int i = 1; i <= N - 1; ++i)ans += phi[i] * 2;
printf("%d\n", ans + 1);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
例题 #2 LG-P2568 GCD
给定 $ n $，求满足 $ \gcd(x, y) $ 为质数的有序数对 $ (x, y) $ 有多少种。
我们令 $ m $ 为值域在 $ [1, n] $ 的质数个数，朴素推导：
\[\begin{aligned} &\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) \in P] \\ =& \sum_{i = 1}^n \sum_{j = 1}^n \sum_{p} [\gcd(i, j) = p] \\ =& \sum_{p}\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(\dfrac{i}{p}, \dfrac{j}{p}) = 1] \\ =& \sum_{p}\sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{p} \rfloor} [\gcd(i, j) = 1] \\ \end{aligned} \]然后问题就转化为了 LG-P2158 [SDOI2008] 仪仗队，预处理一下即可。
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define LIM (11000000)
template < typename T = int >
inline T read(void);
int N;
int phi[LIM + 100];
ll ans(0);
ll sum[LIM + 100];
basic_string < int > Prime;
bitset < LIM + 100 > notPrime;
int main(){phi[1] = 1, notPrime[1] = true;
for(int i = 2; i <= LIM; ++i){
if(!notPrime[i])Prime += i, phi[i] = i - 1;
for(auto p : Prime){
if((ll)i * p > LIM)break;
phi[i * p] = i % p ? phi[i] * phi[p] : p * phi[i];
notPrime[i * p] = true;
if(i % p == 0)break;
}
}N = read();
for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + phi[i] * 2;
for(auto p : Prime){
if(p > N)break;
ans += sum[N / p] - 1;
}
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
欧拉定理
若 $ \gcd(a, p) = 1 $，则有 $ a^{\varphi(m)} \equiv 1 \pmod{m} $。
证明待补。
扩展欧拉定理
即：
\[a^b = \left\{ \begin{array}{ll} a^{b \bmod{\varphi(p)}} & \gcd(a, p) = 1 \\ a^b & \gcd(a, p) \neq 1 \land b \lt \varphi(p) \\ a^{b \bmod \varphi(m) + \varphi(m)} & \gcd(a, p) \neq 1 \land b \ge \varphi(p) \end{array} \right. \]一般用于在快速幂时幂次过高的情况。
证明待补。
乘法逆元
对于线性同余方程 $ ax \equiv 1 \pmod{p} $，则称 $ x $ 为 $ a $ 在模 $ p $ 意义下的乘法逆元，记作 $ a^{-1} $。一般用于解决除法中不适用于分子分母同时取模的缺陷。
首先若 $ p $ 为质数，且 $ a, p $ 互质，那么考虑使用费马小定理，$ a^{p - 1} \equiv 1 \pmod{p} \iff a \times a^{p - 2} \equiv 1 \pmod{p} $。那么 $ a^{-1} = a^{p - 2} $，也就是说 $ a $ 在模 $ p $ 意义下的乘法逆元为 $ a^{p - 2} $。
考虑更一般的情况，若不满足 $ p $ 为质数，但满足 $ a \perp p $，则可以考虑使用 exgcd，即求出 $ ax + py = 1 $ 的 $ x $ 的最小非负解，则有 $ a^{-1} = x $。
而对于更加一般的情况，可以发现其不存在乘法逆元。
CRT（中国剩余定理）
大致就是要解决如下同余式：
\[\left\{ \begin{array}{c} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{array} \right. \]其中满足 $ m_1, m_2, \cdots, m_n $ 两两互质。
大致的思路就是考虑对问题进行拆分，显然若拆分为 $ x_1 \equiv 1 \pmod{m_1}, x_1 \equiv 0 \pmod{m_r}(r \neq 1) $，对于 $ x_2, x_3, \cdots, x_n $ 同理定义，此时 $ x = \sum_{i = 1}^n a_i x_i $ 即为答案。
我们单独考虑一个 $ x_1 $，显然其应为 $ m_2, m_3, \cdots $ 的倍数，令 $ p = \prod_{i = 2}^n m_i $，则应有 $ x_1 = kp $，即 $ kp \equiv 1 \pmod{m_1} $，则 $ k $ 为 $ p $ 在模 $ m_1 $ 意义下的逆元。
更具体地说，假设 $ M = \prod m_i $，那么应有 $ x_i = \dfrac{M}{m_i}(\dfrac{M}{m_i})^{-1} $，注意这里的逆元是模 $ m_i $ 意义下的，但此乘积不能对 $ m_i $ 取模（对于这里的不能取模再详细解释一下，即我们这里是想要求出 $ k $ 与 $ p $ 并乘起来，而不是想要求 $ kp \bmod{m_i} $，我们只是知道 $ k $ 与 $ p $ 在模 $ m_i $ 意义下互为逆元。换句话说如果直接乘起来就会变成 $ 1 $ 了）。
最终 $ \sum_{i = 1}^n a_ix_i \bmod{M} $ 即为模 $ M $ 意义下的唯一解。
同时注意这里只满足 $ m_i $ 之间互质，但不满足 $ m_i $ 为质数，则只能用 exgcd 求解乘法逆元，不能使用费马小定理。
LG-P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪。
int N;
int A[20], B[20];
ll mul(1);
ll ans(0);
void exgcd(ll a, ll b, ll &x, ll &y){
if(!b)return x = 1, y = 0, void();
exgcd(b, a % b, x, y);
ll tmp(x);
x = y, y = tmp - a / b * y;
}
ll CalInv(ll a, ll b){
ll x, y; exgcd(a, b, x, y);
ll mod = b / __gcd(a, b);
return (x % mod + mod) % mod;
}
int main(){
N = read();
for(int i = 1; i <= N; ++i)A[i] = read(), B[i] = read();
for(int i = 1; i <= N; ++i)mul *= A[i];
for(int i = 1; i <= N; ++i)(ans += B[i] * (mul / A[i]) * CalInv(mul / A[i], A[i]) % mul) %= mul;
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
Garner算法
首先同样存在如下同余式：
\[\left\{ \begin{array}{c} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{array} \right. \]我们的目的是将 $ x $ 拆分为若干质数，则有结论，若 $ x \lt \prod m_i $，我们可以将 $ x $ 拆分（称作混合基数表示）为：
\[x = x_1 + m_1x_2 + m_1m_2x_3 + \cdots + m_1m_2\cdots m_{k - 1}x_k \]可以进行如下拆分的正确性也较为显然，首先考虑 CRT，我们需要表示出所有满足 $ x_1 \equiv a_1, x_2 \equiv a_2, \cdots $，于此我们考虑经典的群论套路，任意的 $ x_1 \bmod{m_1} $ 一定可以表示出 $ a_1 $，而 $ m_1x_2 $，因为 $ m_1 \perp m_2 $，则 $ km_1 \bmod{m_2} $ 的环有且仅有一个，所以 $ m_1x_2 $ 可以表示出模 $ m_2 $ 意义下的所有数，包括 $ a_2 $，同理 $ m_1m_2 \perp m_3 $，以此类推。
则也类似这个思路，不难想到 $ x_1 \equiv a_1 \pmod{m_1}, m_1x_2 \equiv a_2 \pmod{m_2}, \cdots \ $。
我们令 $ inv(i, j) $ 表示 $ i $ 在 $ j $ 意义下的逆元，则：$ x_2 = a_2 \times inv(m_1, m_2) \bmod{m_2}, x_3 = a_2 \times inv(m_1, m_3) \times inv(m_2, m_3) \bmod{m_3}, \cdots $。
于是现在我们就成功地用大量小质数表示出一个大整数。
exCRT（扩展中国剩余定理）
还是一样的同余式：
\[\left\{ \begin{array}{c} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{array} \right. \]但是不满足 $ m_1, m_2, \cdots, m_n $ 之间两两互质。
虽然是 exCRT 但是除了问题相似之外与 CRT 似乎没什么关系。
首先考虑存在两个同余方程：
\[\left\{ \begin{array}{c} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{array} \right. \]考虑对于线性同余方程的常规转化：
\[\left\{ \begin{array}{c} x = a_1 + b_1m_1 \\ x = a_2 + b_2m_2 \end{array} \right. \]有：$ a_1 + b_1m_1 = a_2 + b_2m_2 $，整理得到 $ b_1m_1 + (-b_2)m_2 = a_2 - a_1 $。
可以用 exgcd 求得 $ b_1m_1 + (-b_2)m_2 = \gcd(m_1, m_2) $ 的解 $ b_1', b_2' $，同时有 $ d = \dfrac{a_2 - a_1}{\gcd(m_1, m_2)} $，于是有：
\[(db_1')m_1 + (db_2')m_2 = a_2 - a_1 \]所以现在我们以 $ x = a_1 + b_1m_1 $ 为例，我们显然要最小化 $ b_1 $，于是我们取方程中 $ b_1' $ 的最小非负解，或者说实际上取得应为 $ db_1’ $ 的最小非负解，即 $ b_1 = db_1' $。
Tips：读到这里不难发现，若不满足 $ \gcd(m_1, m_2) \mid a_2 - a_1 $，则方程无解。
于是此时我们可以根据 $ b $ 得出一个满足上述两个同余方程的特解 $ x' $，且可以证明对于上述同余方程的所有解 $ x $，有 $ x = x' + k \operatorname{lcm}(m_1, m_2) $，即：
\[x \equiv x' \pmod{\operatorname{lcm}(m_1, m_2) } \]此时两个方程被合成为了同一个，直到最终仅剩一个方程时其解即为答案。
void exgcd(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y){
if(!b)return x = 1, y = 0, void();
exgcd(b, a % b, x, y);
__int128_t tmp(x);
x = y;
y = tmp - a / b * y;
}
void Query(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y, __int128_t c){
exgcd(a, b, x, y);
__int128_t d = c / __gcd(a, b);
x *= d, y *= d;
__int128_t val = b / __gcd(a, b);
x = (x % val + val) % val;
y = (c - a * x) - b;
}
int N;
__int128_t rem1(-1), mod1(-1);
int main(){
N = read();
while(N--){
__int128_t mod2 = read < ll >(), rem2 = read < ll >();
if(!~rem1 || !~mod1){rem1 = rem2, mod1 = mod2; continue;}
__int128_t b1, b2;
Query(mod1, -mod2, b1, b2, rem2 - rem1);
rem1 = rem1 + b1 * mod1;
mod1 = mod1 * mod2 / __gcd(mod1, mod2);
rem1 = (rem1 % mod1 + mod1) % mod1;
}printf("%lld\n", rem1);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
UPD
update-2023__ 初稿
标签：gcd,数论,sum,varphi,int,pmod,浅析,equiv From： https://www.cnblogs.com/tsawke/p/17180266.html