普及组算法：简单数论 & 并查集

简单数论

一点都不简单

欧几里得算法

又称辗转相除法
迭代求两数 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;
}