前言
因为 \(2025\) 届暑假的时候 tad 疯狂的在讲课，而且用了很多高端的东西和证明导致我在暑假的时候数论板块几乎没有听懂，所以我决定写下这篇文章不让当时的悲剧重演。
本篇文章都只讲结论，因为证明分复杂而且没有什么用，在暑假记住结论就好了，至于证明的坑后面会填。
欧拉函数
欧拉函数 \(\varphi (n)\) 定义为小于或等于 \(n\) 且与 \(n\) 互质的正整数的个数。
欧拉函数之所以需要学，就是因为它又一些奇奇怪怪的性质：
- 如果 \(p\) 是质数，那么 \(\varphi(p)=p-1\)。
- \(\varphi\) 是积性函数，即如果 \(\gcd(a,b)=1\) 那么 \(\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b)\)。
- 对于任意 \(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。这个问题可以通过以下步骤解决：
-
计算 \(\gcd(a,n)\)：首先，我们需要计算 \(a\) 和 \(n\) 的最大公约数 \(d\)。这可以通过欧几里得算法实现。
-
检查 \(b\) 是否是 \(d\) 的倍数：如果 \(b\) 不是 \(d\) 的倍数，那么这个同余方程无解。因为如果 \(ax\) 除以 \(n\) 的余数为 \(b\)，那么 \(b\) 必须是 \(a\) 的倍数。但是，如果 \(b\) 是 \(d\) 的倍数，那么我们可以继续下一步。
-
求解同余方程：然后，我们需要求解同余方程 \(ax' \equiv b' \pmod {n'}\)，其中 \(x' = x/d\)，\(b' = b/d\)，\(n' = n/d\)。
-
找到最小的正整数解：最后，我们需要找到最小的正整数解。这可以通过对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;
}