欧几里得算法
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。
gcd(a,b)=gcd(b,a%b)
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
裴蜀定理
裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.
来看一道模板题：
P4549 【模板】裴蜀定理
对应这一推论：
所以题目在题目限制下的最小值就是这n个数的最大公约数。
#include <bits/stdc++.h>
using namespace std;
int n;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
scanf("%d", &n);
int ans = 0, tmp;
for (int i = 1; i <= n; i ++) {
scanf("%d", &tmp);
if (tmp < 0) tmp = - tmp;
//都变为正数不影响结果
ans = gcd(ans, tmp);
}
printf("%d\n", ans);
return 0;
}
扩展欧几里得算法
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
先看代码：
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
int g = exgcd(b, a % b, x, y);
int tmp = x; x = y; y = tmp - a / b * y;
return g;
}
推导过程：
ax + by = gcd(a, b) //1
bx` + (a % b)y` = gcd(b, a % b) //2
联立1，2 得：
ax + by = bx` + (a % b)y`
ax + by = bx` + (a - a / b * b)y`
ax + by = ay` + b(x` - a / b * y`)
对比系数可得：
x = y` y = x` - a / b * y`
所以我们可以用x`和y`倒推x和y，通过欧几里得算法，利用b = 0时
的解x = 1, y = 0往前逐步倒推，最终得到ax + by = gcd(a, b)的
一组整数解
模板题：P1082 [NOIP2012 提高组] 同余方程
code：
#include <bits/stdc++.h>
using namespace std;
int a, m, x, y;
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
int g = exgcd(b, a % b, x, y);
int tmp = x; x = y; y = tmp - a / b * y;
return g;
}
int main() {
cin >> a >> m;
int g = exgcd(a, m, x, y);
cout << (x % m + m) % m;
return 0;
}
费马小定理
费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。
乘法逆元的几种求法
1.扩欧
#include <bits/stdc++.h>
//扩展欧几里得算法求逆元（适用条件：a,p互质，即gcd(a,p)=1）
using namespace std;
int a, p, x, y;
int ecgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int g = exgcd(b, a % b, x, y);
int tmp = x; x = y; y = tmp - (a / b) * y;
return g;
}
int main() {
scanf("%d %d", &a, &p);
int g = exgcd(a, p, x, y);
//用扩欧求ax+bp=gcd(a,p)=1的一组解，此时的x就是a在模p意义下的逆元
printf("%d\n", (x % p + p) % p);
return 0;
}
2.费马小定理
#include <bits/stdc++.h>
//费马小定理求逆元（适用条件：p为质数且a不是p的倍数）
//a在模p意义下的逆元就是a^(p-2)
using namespace std;
int a, p;
int ksm(int a, int b, int c) {//快速幂
int ans = 1;
a = a % c;
while (b) {
if (b & 1) ans = (ans * a) % c;
a = (a * a) % c;
b >>= 1;
}
return ans;
}
int main() {
scanf("%d %d", &a, &p);
printf("%d\n", ksm(a, p - 2, p));
return 0;
}
3.线性递推求1~n的逆元
#include <bits/stdc++.h>//线性递推求逆元
#define ll long long
using namespace std;
const int N = 3e6 + 10;
int n, p, inv[N];
int main() {
ios::sync_with_stdio(false);
cin >> n >> p;
inv[1] = 1;
for (int i = 2; i <= n; i ++)
inv[i] = (ll) (p - p / i) * inv[p % i] % p;
for (int i = 1; i <= n; i ++)
cout << inv[i] << '\n';
return 0;
}
4.倒推
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6 + 10;
int n, p;
ll inv[N], fac[N];
ll ksm(ll x, int y) {
ll ans = 1;
while (y) {
if (y & 1) ans = ans * x % p;
x = x * x % p;
y >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> p;
fac[0] = 1;
for (int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i % p;
inv[n] = ksm(fac[n], p - 2);
for (int i = n; i >= 2; i --) inv[i - 1] = inv[i] * i % p;
for (int i = 1; i <= n; i ++)
cout << fac[i - 1] * inv[i] % p << '\n';
return 0;
}
