数学:简单数论

本教程依据数学:简单数论—洛咕网校所写而成
今天讲了数论, 我有点偷懒
列个大纲, 挖个坑以后再填吧
P.S可以自己百度学习23333

整除

a|b表示a是b的因数,a可以整除b
且|有传递性
即若a|b,b|c,那么a|c

最大公因数 gcd

gcd(n,m) 就是将n和m分别质因数分解, 对于每个因数的指数取n,m中小的那一个
辗转相除法?
欧几里得dalao发明的, 用以快速求两个数的最大公因数.

int gcd(int n,int m)
{
if(m==0)
return n;
else
return gcd(m,n%m);
}

其时间复杂度是O($\log \max(n,m)$)

最小公倍数 lcm

lcm(n,m) 就是将n和m分别质因数分解, 对于每个因数的指数取n,m中大的那一个
并没有很好的方式直接求lcm
但可以通过${lcm(n,m)} \times {gcd(n,m)}=n \cdot m$(可证明,每个因数的指数取n,m大的一个和小的一个就等于两个数都取)来求
即${lcm(n,m)}={(n \times m)} \div {gcd(n,m)}$

快速幂

#include <cstdio>

#define MOD 19260817

int qpow(int x,int p)
{
if(p==1) return x%MOD;
if(p==0) return 1;

int a=qpow(x,p/2);
if(p%2==0) return a*a%MOD;
return a*a%MOD*x%MOD;
}

int main(void)
{
printf("%d\n",qpow(2,11));
}
Author: Odeinjul
Link: http://odeinjul.ooo/lgpj7-2018.html
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.