数论

• $$\gcd(x,y) = \gcd(y,x \% y)$$

• 求解 $ax+by = \gcd(a,b)$。

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

• $$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$$

  int a1,b1;
  void sol(int a2,int b2){
  	int x,y,d=__gcd(a1,a2),na; exgcd(a1,a2,x,y);
  	x=(x*(b2-b1)/d%a2+a2)%a2;
  	na=a1/d*a2,b1=((x*a1%na+b1)%na+na)%na,a1=na;
  }

• $$a^b \equiv a^{b \% \varphi(p) + [b \ge \varphi(p)]\varphi(p)} \mod p$$

• exBSGS，每次除去 $\gcd$ 递归下去直到互质。

• 满足 $a^x \equiv 1 \mod m$ 的最小正整数 $x$，叫做 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。$a$ 与 $m$ 互质是阶存在的充要条件。可以用 BSGS 求解。

• 满足 $\delta_m(g) = \varphi(m)$ 的 $g$ 称为 $m$ 的原根。

  原根判定可以枚举 $\varphi(m)$ 的质因数 $p$，看是否有 $g^{\frac{\varphi(m)}{p}} \equiv 1 \mod m$。

  最小的原根很小，可以枚举求解。

  原根满足 $g^0,g^1,…,g^{\varphi(m)-1}$ 在模 $m$ 意义下互不相同，$m$ 是质数的话可以乘法转加法。