分类: 第一章 基础数论

4 篇文章

第一节 基础方法
最大公约数 欧几里得算法 int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } 扩展欧几里得算法 求 $ax+by=c$ 的解以及逆元($a,b,c>0,c=gcd(a,b)$) // 返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y; int exgcd(…
第三节 同余(一)
中国剩余定理 tips 对于模数不为质数的问题进行求解,我们可以将其因式分解为几个互质的数 (例:$1e9=5^9\times 2^9$),分别在小模数下应用某些技巧求解 (例:卢卡斯定理,暴力等),最后通过 CRT 合并答案。 O(1)快速乘 用于解决中间过程的乘法超出 $2^{64}$ 范围。 inline ll mul(ll x, ll y,…
第四节 同余(二)
二次剩余 洛谷P5491 【模板】二次剩余 题目大意 求 $x^2\equiv N\pmod p$ 的解。 typedef long long ll; typedef pair<ll, ll> pll; #define mp make_pair namespace Complex { ll mod, W, W0; struct comp…