2024基地校Day3

整除 如 a|b 表示 b \mod a = 0
同余 a\equiv b(\mod m) 表示a \mod m = b \mod m
关于同余
如果有
a \equiv b(\mod m)
则有
a+c \equiv b+c(\mod m)
$a c \equiv b c(\mod m)a^c \equiv b^c(\mod m)$
辗转相除法求gcd

int gcd(int n,int m)
{
    if(m == 0) return n;
    if(m > n) swap(n,m);
    int r=n%m;
    return gcd(m,r);
}

exgcd……