目录

模运算

快速幂

gcd和lcm

exgcd

同余与逆元

---

模运算

快速幂

迭代（原理：位运算）

#include <iostream>
using namespace std;
int power(int a, int n)
{int ans = 1;while (n){if (n % 2 == 1){ans *= a;}n /= 2;a *= a;}return ans;
}
int main()
{int n;int a;cin >> a >> n;cout << power(a, n);return 0;
}

gcd和lcm

int gcd(int a, int b)
{while (a){int t = b % a;b = a;a = t;}return b;
}

辗转相除法：gcd(a,b)=gcd(b,a mod b);

更相减损术：gcd(a,b)=gcd(b,a-b);

lcm(a,b)=(a/gcd(a,b))*b;

exgcd

设a,b是两个不全为0的整数，存在整数x,y，使ax+by=gcd(a,b);

即二元一次方程ax+by=(a,b)有整数解

二元一次不定方程ax+by=c,a!=0&&b!=0,若有整数解x=x0,y=y0,则所有整数解为x=x0-b1t,y=y0+a1t,a1=a/gcd(a,b),b1=b/gcd(a,b)

ax+by=c有整数解的充要条件是（a,b）|c

同余与逆元

若m|a-b,则a,b对m同余

若a和b对m同余，则gcd(a,m)=gcd(b,m)，

若a和b对m同余，则ak和bk对m同余，

若a和b对m同余，且a和b有一公因数d，gcd(m,d)=1，a1=a/d,b1=b/d则a1和b1对m同余

ax和1对m同余，x为a mod m的逆元，则gcd(a,m)=1