- 数论基础
- 线性同余方程的求解
- 高次同余方程的求解
- 同余方程组的求解
- 组合数取摸
- 幂取摸
数论基础
整除及其性质
def
对于式子
当
con
同余
def
对于式子
则有
con
线性同余方程的求解
gcd 算法
算法作用
求
算法原理
欧几里得定理
定理内容
定理证明
先证
设
则
可以发现欧几里得定理与上述定理本质相同
算法实现
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
当
每次取摸,时间复杂度
exgcd 算法
算法作用
判断与求不定方程
算法引理
裴蜀定理
定理内容
有整数解,当且仅当
定理证明
设
则显然有
则
则若原式有解,则必须满足
定理推论
算法原理
我们要求
我们猜想,既然求解
那么我们设
由欧几里得定理可以知道
所以
注意到
所以上式化为
整理得
那么可以发现一组特解
所以我们可以在递归右边的同时递归左边,解出这个方程
算法实现
pii exgcd(int a, int b) {
if (b == 0) return mp(1, 0);
pii tmp = exgcd(b, a % b);
pii res = mp(tmp.second, tmp.first - a / b * tmp.second);
return res;
}
时间复杂度
高次同余方程的求解
BSGS
算法作用
求解高次方程
其中
算法原理
令
设
方程转化为
打开得
我们枚举
再枚举
感性的来说,就是分块思想在指数上的应用
算法实现
ll qpower(ll a, ll x, ll m) {
ll res = 1;
if (x == 0) return 1;
while (x) {
if (x & 1) res = res * a % m;
a = a * a % m, x >>= 1;
}
return res% m;
}
ll bsgs(ll a, ll b, ll m) {
unordered_map<ll, int> lst; lst.clear();
ll d = ceil(sqrt(m));
for (int j = 0; j <= d - 1; ++j) {
lst[b * qpower(a, j, m) % m] = j;
}
ll tmp = qpower(a, d, m);
if (tmp == 0) return b == 0 ? 1 : -1;
for (int i = 0; i <= d; ++i) {
ll val = qpower(tmp, i, m);
if (lst.find(val) != lst.end() && i * d - lst[val] >= 0) return i * d - lst[val];
}
return -1;
}
时间复杂度
同余方程组的求解
CRT
算法作用
求解同余方程组
其中
算法原理
令
则解为
本质上是对于互不影响的
算法实现
pii exgcd(int a, int b) {
if (b == 0) return mp(1, 0);
pii tmp = exgcd(b, a % b);
pii res = mp(tmp.second, tmp.first - a / b * tmp.second);
return res;
}
void CRT() {
for (int i = 1; i <= n; ++i) {
int inv = exgcd(prod / m[i], m[i]), inv = (inv % m[i] + m[i]) % m[i];
ans += (((a[i] * prod) % m[i] + m[i]) % m[i] / m[i] * inv % m[i] + m[i]) % m[i];
}
}
时间复杂度
exCRT
算法作用
求解同余方程组
其中
算法原理
与 CRT 类似,exCRT 本质上仍然是一个回带的过程
对于两个方程
假设我们已经解出了
的方程
且令
我们有理由相信解出的
的形式表达出
那么在考虑第
整理得
即可由 exgcd 求解
算法实现
#include <bits/stdc++.h>
#define pbb pair<__int128, __int128>
#define mp make_pair
using namespace std;
typedef __int128 bint;
const bint maxn = 2e5 + 10;
bint n, a[maxn], b[maxn], ans, prod;
bint read() {
char ch = getchar(); bint x = 0, f = 1;
while (ch < '0' || '9' < ch) { if (ch == '-') f = -f; ch = getchar(); }
while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0', ch = getchar(); }
return x * f;
}
void out(bint x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
bint gcd(bint a, bint b) { return b ? gcd(b, a % b) : a; }
pbb exgcd(bint a, bint b) {
if (b == 0) return mp(1, 0);
pbb tmp = exgcd(b, a % b);
pbb ans = mp(tmp.second, tmp.first - a / b * tmp.second);
return ans;
}
bint mul(bint a, bint b, bint mod) {
bint res = 0;
while(b) {
if(b & 1) res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}
void exCRT(bint k) {
bint B = ((a[k] - ans) % b[k] + b[k]) % b[k];
bint GCD = gcd(prod, b[k]);
pbb sol = exgcd(prod, b[k]);
sol.first = mul(sol.first, B / GCD, b[k]);
ans += prod * sol.first, prod *= b[k] / GCD;
ans = (ans + prod) % prod;
}
int main() {
n = read();
for (int i = 1; i <= n; ++i) b[i] = read(), a[i] = read();
ans = a[1], prod = b[1];
for (int i = 2; i <= n; ++i) {
exCRT(i);
}
out(ans);
return 0;
}
时间复杂度
组合数取模
卢卡斯定理
算法作用
求
算法原理
经过一系列推到可知
算法实现
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
ll n, m, p, prod[maxn], inv[maxn];
void clear() { memset(prod, 0, sizeof prod); memset(inv, 0, sizeof inv); }
ll lucas(ll n, ll m) {
if (m < n) return 0;
if (m < p) return prod[m] * inv[n] % p * inv[m - n] % p;
return lucas(n % p, m % p) * lucas(n / p, m / p) % p;
}
void solve() {
scanf("%lld %lld %lld", &n, &m, &p); clear();
prod[0] = inv[0] = prod[1] = inv[1] = 1;
for (int i = 2; i <= min(m + n, p); ++i) prod[i] = prod[i - 1] * i % p;
for (int i = 2; i <= min(m + n, p); ++i) inv[i] = (p - p / i) * inv[p % i] % p;
for (int i = 2; i <= min(m + n, p); ++i) inv[i] = inv[i - 1] * inv[i] % p;
printf("%lld\n", lucas(m, n + m));
}
int main() { ll t;
scanf("%lld", &t);
while (t --) solve();
return 0;
}
时间复杂度
扩展卢卡斯定理
幂取摸
欧拉定理
定理内容
定理证明
易知
又由于
所以
所以得证
orz不会-
orz不会-
Orz