亿点数论

常见数学符号

1. $x|y$, $x$ 整除于 y,$x$ 是 $y$ 的因数
2. $x\bot y$, $x$ 和 $y$ 互质
3. $\sum$ 求和
4. $\prod$ 求乘积,如: $\prod^n_{i=1}$表示 $n!$
5. $\Delta$ 表示变化或差异

快速幂

求 $a^b$？
如果 $b$ 是偶数：$a^b=(a^2)^{b/2}$
如果 $b$ 是奇数：$a^b=a \times (a^2)^{b/2}$
例如：$x^{20} = (x^2)^{10} = (x^4) ^ 5 = x^4 * (x^8)^2 = x ^ 4 \times (x ^ {16}) ^ 1$

long long x ,p ,m, ans=1;
cin >> x >> p >> m;
while(p != 0) {
    if(p % 2 == 1) ans = ans * x % m;
    x = x * x % m;
    p = p / 2;
}

同余以及扩展欧几里得算法

什么是同余

$a$,$b$ 除以 $m$ 的余数相等,则称 $a$ 和 $b$ 对于模 $m$ 同余 或 $a$ 同余 $b$ 模 $m$
记作 $a\equiv b(mod~m)$

同余的性质

1. 对称性: $a\equiv b(mod~m)$ -> $b\equiv a(mod~m)$
2. 传递性 $a\equiv b(mod~m)$, $b\equiv c(mod~m)$ -> $a\equiv c(mod~m)$
3. 相加性 $a\equiv b(mod~m)$ -> $a+c\equiv b+c(mod~m)$
4. 同乘 (如上)
5. 同幂 (如上)

裴蜀定理

裴蜀定理：设 a,b不全都为0 ，存在整数 x,y ，使得 $a \times x + b \times y = gcd(a, b)$。

总结 ： 对于 $a \times x + b \times y = gcd(a, b) $ 中其中一组解
1. 如果 $b = 0$ 则 $x = 1, y = 0$
2. 其他情况 通过 $x = y$ , $y = x -a /b * y$ 递归求解

设 $x1, y1$ 为 $ax+by = d$ 的一组解，则通解为
$x = x1 + k \times b \div d$
$y = y1 - k \times a \div d$

扩欧

int exgcd(int a, int b, int &x,int & y){
	if(b  == 0) {
		x = 1,y = 0;
		return 0;
	}
 	int d = exgcd(b, a % b,x ,y);
	int t = x;
	x = y, y = t - a / b * y;
	return d; 
}