简单数论
一点都不简单
欧几里得算法
又称辗转相除法
迭代求两数 gcd 的做法
由 $(a, b) = (a, ka + b)$ 的性质：$\gcd(a, b) = \gcd(b, a\bmod b)$
容易证明这么做的复杂度是 $O(\log n)$
注意：$\gcd(0, a) = a$
裴蜀定理
设(a, b) = d，则对任意整数x, y，有d|(ax + by) 成立；
特别地，一定存在x, y 满足ax + by = d
等价的表述：不定方程ax + by = c(a, b, c 为整数) 有解的充要条件为(a, b)|c
推论：a, b 互质等价于ax + by = 1 有解
P4549 【模板】裴蜀定理
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n; scanf("%d", &n); int a; scanf("%d", &a); int g = a;
for(int i=2; i<=n; ++i) {
scanf("%d", &a); if(a == 0) continue;
if(a < 0) a = -a;
g = __gcd(g, a);
}
printf("%d\n", g);
return 0;
}扩展欧几里得
考虑如何求得ax + by = d 的一个解。这里d = (a, b)
考虑使用欧几里德算法的思想，令a = bq + r，其中r = a mod b；
递归求出bx + ry = d 的一个解。
设求出bx + ry = d 的一个解为x = x0, y = y0，考虑如何把它变形成ax + by = d 的解。
将a = bq + r 代入ax + by = d，化简得b(xq + y) + rx = d
我们令xq + y = x0, x = y0，则上式成立
故x = y0, y = x0 - y0q 为ax + by = d 的解
边界情况：b = 0 时，令x = 1, y = 0
P1082 同余方程
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll a, b;
pll exgcd(ll a, ll b) {
if(b == 0) return {1,0};
pll p = exgcd(b, a%b);
return {p.second, p.first-a/b*p.second};
}
int main() {
scanf("%lld%lld", &a, &b);
ll x = exgcd(a,b).first;
while(x < 0) x+=b;
while(x-b > 0) x-=b;
printf("%lld\n", x);
return 0;
}求不定方程所有解
怎么求ax + by = c 的所有解？
先用exgcd 求出任意一个解x = x0, y = y0
再求出ax + by = 0 的最小的解
x = dx = b/(a, b), y = dy = -a/(a, b)
所有解就是x = x0 + kdx, y = y0 + kdy, k 取任意整数
逆元
若ax ≡ 1(mod b)，则称x 是a 关于模b 的逆元，
常记做a−1。
回忆同余的性质。上式等价于ax + by = 1
如何求逆元？等价于解方程ax + by = 1
因此逆元不一定存在：
存在的充要条件为(a, b) = 1
推论：p 是质数，p 不整除a，则a 模p 的逆元存在。
结论：在[0, b) 的范围内，a 关于模b 的逆元(若存在) 是唯一的。
证明：
反证法，若a 有两个逆元0 < x1 < x2 < b，
即ax1 ≡ ax2 ≡ 1(mod b)，
那么有b|a(x2 − x1) 成立
又由于(a, b) = 1，因此b|(x2 − x1)。
其中0 < x2 − x1 < b，产生了矛盾。
P3811 【模板】乘法逆元
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
long long inv[int(3e6+10)]; int n, p;
int main() {
scanf("%d%d", &n, &p);
inv[1] = 1;
for(int i=2; i<=n; ++i) {
inv[i] = p-(p/i)*inv[p%i]%p;
}
for(int i=1; i<=n; ++i) printf("%lld\n", inv[i]);
return 0;
}中国剩余定理
咕咕咕
杂题
如果看第一眼不会做，一般就得想一年的题，如臭名昭著的小凯类数论问题
P4942 小凯的数字
我们知道，一个数模9等于他的各位和模9。这一结论可以推广至将某数截成若干节，每段合起来也符合这个规律，题目便转化成求sigma [l..r]。用 __int128 也可以过，但是更好是把除以二挪到前面，使其符合乘法取模分配率，注意奇偶。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long LL;
int a[15], b[15];
int main() {
int q; scanf("%d", &q);
for(int i=1; i<=q; ++i) { LL l, r;
scanf("%lld%lld", &l, &r);
if((r-l+1) %2 == 0) printf("%lld\n", ((r-l+1)/2)%9*(l+r)%9);
else printf("%lld\n", ((l+r)/2)%9*(r-l+1)%9);
}
return 0;
}P3951 小凯的疑惑
17年提高组出了好多屑题啊。。。这题连部分分都不给
而且我到现在还不会做。。。要是今年还出数论题估计就凉了 /kk
咕咕咕
并查集
裸题已经很少见了，但NOIp2017就出了这么一道。
P3958 奶酪
特点是自底至上找出通路，可以联想至森林合并。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1100;
struct node {
LL x, y, z;
} a[N];
bool cmp(node a, node b) {
return (a.z < b.z);
}
bool tp[N], bt[N];
int fa[N], T, n;
LL h, r;
int root(int x) {
return fa[x]==x?x:root(fa[x]);
}
bool check(int i, int j) {
LL dist = (a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y) + (a[i].z-a[j].z)*(a[i].z-a[j].z);
return dist <= 4*r*r;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%lld%lld", &n, &h, &r);
memset(bt, false, sizeof bt);
memset(tp, false, sizeof tp);
for(int i=1; i<=n; ++i)
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
sort(a+1, a+n+1, cmp);
for(int i=1; i<=n; ++i) {
if(a[i].z - r <= 0) bt[i] = true;
if(a[i].z + r >= h) tp[i] = true;
}
for(int i=1; i<=n; ++i) fa[i] = i;
for(int i=1; i<=n; ++i) {
for(int j=i+1; j<=n; ++j) {
if(check(i, j)) {
fa[root(i)] = root(j);
}
}
}
bool fla = false;
for(int i=1; i<=n; ++i) {
if(bt[i] && tp[root(i)]) {
fla = true;
break;
}
}
printf("%s", (fla ? "Yes\n" : "No\n"));
}
return 0;
}
