一。数论基础
1)数论函数
数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。
2)积性函数
如果对于f(n),f(1)=1,若(x,y)=1则f(xy)=f(x)f(y),称其为积性函数。
如果对于f(n),f(1)=1,有f(xy)=f(x)f(y),称其为完全积性函数。
二。约数
最大公约数
求最大公约数:欧几里得算法 gcd(a,b)=gcd(b,a%b)
点击查看代码
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
点击查看代码
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}
同余
裴蜀定理:设 a,b 是不全为零的整数,对任意整数 x,y,满足 gcd(a,b)|ax+by,且存在整数 x,y, 使得ax+by=gcd(a,b).
推广:逆定理:若a,b为不全为零的整数,若d>0是a,b的公因子,且存在整数x,y,使得ax+by=d,则d=gcd(a,b)
特殊的,设a,b为不全为零的正整数,若存在x,y,使得ax+by=1则a,b互质。
裴蜀定理可以推广到多个整数
//补不完了,先学新课吧。
原根
筛法