# 简单数论

一点都不简单

# 欧几里得算法

又称辗转相除法
迭代求两数 gcd 的做法
(a,b)=(a,ka+b)(a, b) = (a, ka + b) 的性质:gcd(a,b)=gcd(b,amodb)\gcd(a, b) = \gcd(b, a\bmod b)
容易证明这么做的复杂度是 O(logn)O(\log n)

注意:gcd(0,a)=a\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;
}
更新于