前言

因为 $2025$ 届暑假的时候 tad 疯狂的在讲课，而且用了很多高端的东西和证明导致我在暑假的时候数论板块几乎没有听懂，所以我决定写下这篇文章不让当时的悲剧重演。

本篇文章都只讲结论，因为证明分复杂而且没有什么用，在暑假记住结论就好了，至于证明的坑后面会填。

欧拉函数

欧拉函数 $\varphi (n)$ 定义为小于或等于 $n$ 且与 $n$ 互质的正整数的个数。

欧拉函数之所以需要学，就是因为它又一些奇奇怪怪的性质：

1. 如果 $p$ 是质数，那么 $\varphi(p)=p-1$。
2. $\varphi$ 是积性函数，即如果 $\gcd(a,b)=1$ 那么 $\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b)$。
3. 对于任意 $n$ 满足 $\sum_{d\mid n}\varphi(d)=n$，$a|b$ 的意思是 $\gcd(a,b)=a$。

不定方程

不定方程可以使用 $\operatorname{exgcd}$ 进行求解，先给代码。

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

$\operatorname{exgcd}$ 函数可以求解方程 $ax+by=\gcd(a,b)$（$a,b$ 为常数）的整数根 $x,y$。

调用 exgcd(a,b,x,y) 的返回值为 $\gcd(a,b)$，在调用时 $x,y$ 是没有意义的，在调用之后 $x,y$ 就会成为方程的一组解。

但是如果需要求解 $ax+by=c$，那么我们可以先求解 $ax+by=\gcd(a,b)$，接着将将 $x,y,\gcd(a,b)$ 全部乘以 $\dfrac{c}{\gcd(a,b)}$ 就可以了。

如果 $\dfrac{c}{\gcd(a,b)}$ 不是整数，那么这个方程就无解。

「NOIP2012」同余方程 && 使用 $\operatorname{exgcd}$ 求解逆元

这个题目求解的其实就是 $a$ 在模 $b$ 意义下的逆元。

因为方程保证有解也就是保证 $a$ 有逆元，所以我们可以知道 $\gcd(a,b)$ 一定是 $1$。

同余方程经过变形可以得到 $ax=1+by$，在经过移项得到 $ax+b(-y)=1$。

因为 $y$ 不许要输出所以他的符号可以不管而且 $\gcd(a,b)=1$，那么方程就成为了 $ax+by=\gcd(a,b)$ 了，直接使用 $\operatorname{exgcd}$ 求解。

因为 $x$ 可能不是最小的正整数，所以输出 $(x+b)\%b$ 即可。

一般性同余方程

对于同余方程 $ax \equiv b \pmod n$，我们需要找到一个整数 $x$，使得 $ax$ 除以 $n$ 的余数为 $b$。这个问题可以通过以下步骤解决：

1. 计算 $\gcd(a,n)$：首先，我们需要计算 $a$ 和 $n$ 的最大公约数 $d$。这可以通过欧几里得算法实现。

2. 检查 $b$ 是否是 $d$ 的倍数：如果 $b$ 不是 $d$ 的倍数，那么这个同余方程无解。因为如果 $ax$ 除以 $n$ 的余数为 $b$，那么 $b$ 必须是 $a$ 的倍数。但是，如果 $b$ 是 $d$ 的倍数，那么我们可以继续下一步。

3. 求解同余方程：然后，我们需要求解同余方程 $ax' \equiv b' \pmod {n'}$，其中 $x' = x/d$，$b' = b/d$，$n' = n/d$。

4. 找到最小的正整数解：最后，我们需要找到最小的正整数解。这可以通过对x取模n来实现。

因为这可能不好实现，所以我封装了一个函数。

long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}
long long solve_congruence(long long a, long long b, long long n) {
    long long x, y;
    long long gcd = extended_gcd(a, n, x, y);
    if (b % gcd != 0) {
        return -1;  // 无解
    }
    x *= b / gcd;
    n /= gcd;
    x = (x % n + n) % n;  // 转化为最小的正整数解
    return x;
}

逆元

众所周知同余有很多性质但是都不适用于除法，所以在取模之后就不能使用除法了。

假设你到计算 $\dfrac{x}{a}$ 在对 $mod$ 取模意义下的结果，那么你就不可以直接进行除法操做，而是要计算 $x\cdot \operatorname{inv}(a)\% mod$ 的结果，其中 $\operatorname{inv}$ 表示逆元。

形式化的 $a\cdot \operatorname{inv(b)} \equiv \dfrac{a}{b} \pmod mod$。

在 $b,mod$ 互质时可以使用 「NOIP2012」同余方程 中的扩展欧几里得定理进行求解。

在 $mod$ 为质数是可以使用费马小定理求解，具体来说 $\operatorname{inv(b)}=b^{mod-2}\ \%mod$，可以使用快速幂进行求解。

int inv(int a){
    int ans=1,b=mod-2;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1,a=a*a%mod;
    }
    return ans;
}

当然，在 $mod$ 为质数时还可以地推求逆元。

void pre(int n){
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

组合数

去看大佬的文章吧！！(以下时搬运)

1.常见方法

适用范围：$n$，$m$ 较小

时间复杂度：$O(m)$

ll C(ll n,ll m){
    if(m<0||n<m)return 0;
    if(m>n-m)m=n-m;
    ll i,up=1,down=1;
    for(i=0;i<m;++i){
        up=up*(n-i)%mod;
        down=down*(i+1)%mod;
    }
    return up*inv(down)%mod;
}

依据性质：$\operatorname{C}_n^m=\operatorname{C}_n^{n-m}$，$C\_n^m=\dfrac{n!}{m!(n-m)!}$

2.预处理

适用范围：$n$，$m$ 在 $10^7$ 以内，$mod$ 为质数

时间复杂度：预处理 $O(n)$，调用 $O(1)$

ll jc[N],inv[N];
void prework(ll n){
    ll i;
    inv[0]=jc[0]=inv[1]=1;
    for(i=1;i<=n;++i)jc[i]=jc[i-1]*i%mod;
    for(i=2;i<=n;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(i=1;i<=n;++i)inv[i]=inv[i-1]*inv[i]%mod;
}
ll C(ll n,ll m){
    if(n<m)return 0;
    return jc[n]*inv[m]%mod*inv[n-m]%mod;
}

依据性质：$C_n^m=\dfrac{n!}{m!(n-m)!}$

3.杨辉三角

适用范围：$n$，$m$ 在 $10^3$ 左右。

时间复杂度：预处理 $O(n^2)$，调用 $O(1)$

空间复杂度：$n^2$

int c[N][N];
inline void prework(int n){
    for(int i=0;i<=n;++i)
    for(int j=0;j<=i;++j)
        if(!j)c[i][j]=1;
        else c[i][j]=c[i-1][j]+c[i-1][j-1];
}

依据性质：$C_{n+1}^m=C_n^m+C_n^{m-1}$。

4.lucas定理

适用范围：$n$，$m$ 在 $10^{18}$ 以内，$mod$ 为 $10^{5}$ 以内的质数

时间复杂度：$O(mod\times \log(n))$

ll lucas(ll a,ll b){
    if(a<mod&&b<mod)return C(a,b);
    return C(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;
}

依据性质：

Lucas 定理：如果 $p$ 是素数，对于任意整数 $1 \le m \le n$，都有 $\operatorname{C}_n^m \equiv C_{n \% p}^{m \% p}\ C_{n / p}^{m / p} \; \; (mod \; p)$，其中 $C_{n / p}^{m / p}$ 可以再进行分解，直至 $n$，$m$ 小于 $p$ 为止。

中国剩余定理

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 $n_1, n_2, \cdots, n_k$ 两两互质）：

$\begin{cases} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ &\vdots \\ x &\equiv a_k \pmod {n_k} \\ \end{cases}$

1. 计算所有模数的积 $n$；
2. 对于第 $i$ 个方程：
   1. 计算 $m_i=\dfrac{n}{n_i}$；
   2. 计算 $m_i$ 在模 $n_i$ 意义下的逆元；
   3. 计算 $c_i=m_i\cdot m_i^{-1}$。
3. 方程组在模 $n$ 意义下的唯一解为：$x=\sum_{i=1}^k a_ic_i \pmod n$。

调用下面的函数返回值为 $x$，其中 $a,r$ 为数组名储存的内容与上文一样。

int CRT(int k, int* a, int* r) {
  int n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    int m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}