五一DAY1数论学习笔记
by ruanxingzhi
整除性
如果a能把b除尽，也就是没有余数，则我们称a整除b，亦称b被a整除。（不是除以，是整除！！）
记作：(a|b)
|这个竖杠就是整除符号
整除的性质
- 自反性
对于任意(n),有(n|n).
- 传递性
若有(a|b,b|c),则(a|c).
- 反对称性
如果(a|b),且(b|a),则(a=b)
约数和倍数
如果(a|b)，那么(a)是(b)的约数，(b)是(a)的倍数。称(a)为(b)的因子。
从而得到重要推论：
任何数(n)至少有两个因子：(1)和(n)自身。我们将它们称为(n)的平凡因子。(其他的因子为非平凡因子)
([1,n])的整数中，(k)的倍数有(frac{n}{k})个
计算
如何计算([1,n ])中每个数的约数个数
n的约数个数记为(d(n)).要求给出一个(O(n log n))的算法。
做法：暴力打标记
#include<bits/stdc++.h>
using namespace std;
int d[100005],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;i*j<=n;j++){
d[i*j]++;
}
}
for(int i=1;i<=n;i++){
printf("d[%d]=%d
",i,d[i]);
}
return 0;
}
质数
质数是不存在非平凡因子的数
即只存在1和自己本身这两个约数的数
e.g.
(2.3,5,7,19260817......)
判断质数
求一个数是不是质数(O(sqrt{n}))做法
bool prime(int x){
if(x==1)return false;
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
n的因子成对出现，一般情况下，(n=a*b)，则a，b中一个大于等于(sqrt{n})，一个小于等于(sqrt{n})
如何证明质数有无限个
【反证】假设质数有限
分别为(p_1,p_2,p_3......p_n)
有(m=p_1*p_2*p_3*...*p_n+1)
则(m\%p_1=1,m\%p_2=1,m\%p_3=1.......m\%p_n=1)
质数的性质
设(π(n))为不超过(n)的质数个数。那么有：
$$π(n)simfrac{n}{ln;n}$$
(π(n))是质数分布函数，(n)越大，质数的分布越稀疏
质数判断
朴素想法就是逐个判断，然而它的复杂度是(O(n;sqrt{n}))（It is so big！）
所以我们使用筛法（小学学的，就比如100以内的数筛去2,3,5,7的倍数之后剩下的数就都是质数了）
为什么我们不需要使用4,6,8,9这些合数去筛？
前面我们学过整除的传递性，在这里就能用上了
若(a|b),(b|c),则(a|c)
所以筛了2，一定筛了4,6,8
筛了3时，一定筛掉了6，9
所以这些数早就被筛过了
我们为何要再用他们去筛呢
代码实现
//埃氏筛法求素数
#include<bits/stdc++.h>
using namespace std;
bool notprime[10005]={0};
int main(){
int n,i,a;
cin>>n;
for(a=2;a<=n;a++){
if(notprime[a]==0){
printf("%d ",a);
for(i=2;i*a<=n;i++){
notprime[i*a]=1;
}
}
}
}
更多素数的知识请参考这里
质因数分解
每个数都可以拆成质数乘积的方式。这个过程叫做质因数分解。
(5 = 5 = 5^1)
(15 = 3 * 5 = 3^1 * 5^1)
(36 = 2 * 2 * 3 * 3 = 2^2 * 3^2)
我们可以保证：这样的分解方式是唯一的
质因数分解可以(O（sqrt{n}）)完成
//质因数分解
int work(int x,int p[]){
int cnt=0;
for(int i=2;i*i<=x;i++){
while(x%i==0){
p[cnt++]=i;
x/=i;
}
}
if(x>1)p[cnt++]=i;
return cnt;
}
模
回顾小学除法
一个数除以另一个数，得到商和余数
(17÷5=3......2) -----> (17=lfloorfrac{17}{5} floor*5+17\%5=3*5+2)
普遍的我们可以这样来表示除法：
$$a=lfloorfrac{a}{p} floor * p+a%p$$
其中(p)是除数，(lfloorfrac{a}{p} floor)是商，(a\%p)是余数
显然，如果p能将a整除，那么a ÷ p的余数为0.
也就是说：(p|a)当且仅当(a\%p=0).
所以，我们判断(p)能否整除(a)，就只需要判断(a\%p)是否为(0)。
这很方便用代码实现。
模的性质
- 值域
首先，由于模是取余，所以(a\%p)一定落在([0, p -1])之间。
- 随时取模性质
在只含加法和乘法的式子中，如果最后的运算结果需要对(p)取模，那么你可以在运算过程中随便取模。
只需要最后把结果对(p)再取模，答案就是正确的。
如何保证取模之后得到的数一定是正数？
公式：((a\%b+b)\%b)
GCD与LCM
(gcd(a,b)):(a,b)的最大公因数
(lcm(a,b)):(a,b)的最小公倍数
最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。(a)，(b)的最大公约数记为(（a，b）)，同样的，(a)，(b)，(c)的最大公约数记为(（a，b，c）)，多个整数的最大公约数也有同样的记号。
求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，(a)，(b)的最小公倍数记为([a，b])。
Small Quiz
如果我们把A分解成了(2^{a_1}3^{a_2}5^{a_3}…)
把B分解成了(2^{b_1}3^{b_2}5^{b_3}…)
1、如何快速求(gcd(a,b)?)
设(d=2^{P_1}3^{P_2}5^{P_3}…)
则很容易得到
(P_1le a_1,P_1 le b_1)
(P_2le a_2,P_2 le b_2)
(P_3le a_3,P_3 le b_3…)
所以a,b的最大公因数$$d=2^{min(a_{1},b_1)}3^{min(a_{2},b_2)}5^{min(a_3,b_3)}…$$
2、如何快速求(lcm(a,b)?)
类似的只要把上面的(min)改成(max)就好了
$$c=2^{max(a_{1},b_1)}3^{max(a_{2},b_2)}5^{max(a_3,b_3)}…$$
一个小式子：(gcd(a,b)*lcm(a,b)=a*b)
以a=1008，b=60为例：
(1008=2^43^25^07^1)
(60=2^23^15^17^0)
(gcd(a,b)=2^23^15^07^0=)
(lcm(a,b)=2^43^25^17^1)
(gcd*lcm=2^23^15^07^02^43^25^17^1=1008*60)
如何求GCD
直接给出两个数，如何求(gcd(a,b))?
做法：GCD递归定理
等价的写法:(gcd(a,b)=gcd(a\%b,b))
代码实现
\递归
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
\迭代
int gcd(int m, int n) {
while(m>0) {
int c=%m;
n=m;
m=c;
}
return n;
}
一条性质
记(F[n])为斐波那契数列的第(n)项，则有
$$gcd(F[a],F[b])=F[gcd(a,b)]$$
求lcm
(lcm(a,b)=a/gcd(a,b)*b)