顶函数（\(\lceil {x} \rceil\)）、底函数（\(\lfloor {x} \rfloor\)）：
常称之为高斯（取整）函数。
定义：
顶函数：\(\geq {x}\)的最小整数。
底函数：\(\leq {x}\)的最大整数。
举个例子：
\(1.\lceil {1.5} \rceil=2\)
\(2.\lfloor {1.5} \rfloor=1\)
\(3.\lceil {-1.5} \rceil=-1\)
\(4.\lfloor {-1.5} \rfloor =-2\)
带余除法：
定义:
\(对于任意整数a,b（a\geq b,b\neq 0）,\)\(存在q,r,满足a=qb+r（0\leq r \leq |b|）,且q，r唯一\)
我们把a叫做被除数，b叫做除数，q叫做商，r叫做余数。
可以证明\(q=\lfloor \left (\frac {a}{b}\right )\rfloor,r=a-b\lfloor \left(\frac {a}{b} \right)\rfloor\)（证明如下）
\(\because这个是很显然的\)
\(\therefore q=\lfloor \left (\frac {a}{b}\right )\rfloor,r=a-b\lfloor \left(\frac {a}{b} \right)\rfloor\)
整除：
定义：如果\(a\)能把\(b\)除尽，余数为0，那么就说是\(b\)被\(a\)整除，即\(a|b\)。
整除的性质：
- 自反性：对于任意\(n\)，有\(n|n\)。
- 传递性：若\(a|b,b|c\)，那么\(a|c\)。
- 反对称性：若\(a|b,b|a\)，即\(a=b\)。（对称性：若\(a\)满足\(b\cdots\)关系，那么\(b\)也满足\(a\cdots\)关系）
-
若\(b|a,c|b\)，则\(c|a\)。（证明如下）
\(\because b|a,c|b\)
\(\therefore（所以必然存在两个整数x，y）使得a=xb\)，\(b=yc\)
\(又\therefore a=xyc\)
\(\because a/c=xy\)
\(\therefore c|a\) -
若\(c|a,c|b\)，则对任意数\(x,y\)，必有\(c |（ax+by）。\)（证明如下）
\(\because c|a,c|b\)
\(\therefore （所以必然存在两个整数p，q）使得a=pc\)，\(b=qc\)
\(又\therefore c |（pcx+qcy）\)
\(c|c（px+qy）\)
\(\because 两边都有c\)
\(\therefore c（px+qy）是c的倍数\)
\(又\therefore c|(ax+by)\) -
若\(b|a,a\neq 0\)，则有\(|b| \leq |a|\)。（证明如下）
\(\because b|a\)
\(\therefore （所以必然存在一个整数q）使得a=qb\)
\(又\therefore a是b的倍数，|b| \leq |a|\)。 -
若\(b|a,a\neq 0\)，则\(\left( \frac ab \right)|a\)。（证明如下）
\(\because b|a\)
\(\therefore （所以必然存在一个整数q）使得a=qb\)
\(又\therefore \left( \frac {a}{b} \right)=\left( \frac {qb}{b} \right)=q\)
\(\because a是q的倍数\)
\(\therefore q|a\)
\(又\therefore \left(\frac{a}{b}\right)|a\) -
若\(b|a,c|a,b\bot c\)，则\(bc|a\)。（举例如下）
\(1.当a=12,b=1,c=6时，1|12,6|12,1\bot12,6|12。\)
\(2.当a=72,b=8,c=9时，8|72,9|72,8\bot9,72|72。（自反性：72|72）\) - 若\(a|b,b|a\)，则\(|a|=|b|\)。（反对称性）
-
若\(a|b\)，对任意整数\(c\)，则\(a|bc\)。（证明如下）
\(\because a|b\)
\(\therefore b=xa，b是a的倍数\)
\(又\therefore乘上任意整数c，bc依旧是a的倍数\)
\(又\therefore a|bc\) -
若\(a|b\)，对于任意整数\(m（m\neq0）\)，则\(ma|mb\)。（证明如下）
\(\because 这是显然的\)
\(\therefore ma|mb\)唯一分解定理（算术基本定理）：
\(n=p_1^{r_1}*p_2^{r_2}*\cdots\)
其中\(p_i\)是质数，\(p_1=2,p_2=3 \cdots\)以此类推结论：
设\(p\)为质数，对于任意整数\(a\)，则有\(p|a\)或者\((p,a)=1\)。（证明如下）
\(\because p为质数\)
$\therefore a要么是p的倍数，要么p\perp a。 $
\(又\therefore p|a或者(p,a)=1\)约数和倍数：
推论：
在算术基本定理中，若\(N\)被唯一分解为\(N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}\),其中\(c_i\)是正整数，\(p_i\)是质数且满足\(p_1<p_2<\cdots p_m\),则\(N\)的正整数集合可写作\(：\)
{\(p_1^{b_1}p_2^{b_2}\cdots p_m^{b_m}\)},其中\(0\leq b_i \leq c_i\)
N的正约数个数为\(:\)
\[(c_1+1)*(c_2+1)*\cdots*(c_m+1)=\prod_{i=1}^{m}(c_i+1)\]
\(N\)的所有正约数之和为\(:\)
\[(1+p_1+p_1^2+\cdots+p_1^{c_1})*\cdots*(1+p_m+p_m^2+\cdots+p_m^{c_m})=\prod_{i=1}^{m}(\sum_{j=0}^{c_i}(p_i)^{j})\]定义：
若\(a|b,a\)是\(b\)的约数，\(b\)是\(a\)的倍数，称\(a\)为\(b\)的因子（对于任何数\(n\)，至少有两个因子\(1\)和\(n\)本身，称它们为\(n\)的平凡因子，其他即为非平凡因子）。特别的，任何正整数都是\(0\)的约数。
约数的求法：
1.试除法：
因为约数总是成对出现，所以只需要从\(1\) ~\(\sqrt{n}\)。时间复杂度\(:O(\sqrt{n})\)
#include"bits/stdc++.h"
#include<time.h>
using namespace std;
#define N 10086
int a[N];
int n;
int cnt=0;
int main(void) {
ios::sync_with_stdio(false);
cin>>n;
//clock_t start = clock();
for(int i=1; i<=sqrt(n); ++i) {
if(n%i==0) {
a[++cnt]=i;
if(n/i!=i) a[++cnt]=n/i;
}
}
for(int i=1; i<=cnt; ++i) cout<<a[i]<<" ";
//clock_t ends = clock();
//cout<<"\n Running time: "<<(double)(ends - start)/ CLOCKS_PER_SEC;
return 0;
}2.倍数法：
如果更改题意，给出\(l,r\)，要求求\(l-r\)之间的每个数的正约数集合。那么再用试除法，时间复杂度就为\(O(N\sqrt{N})\)，变得有点恶心，特别是在\(N\)非常大的时候。譬如跑\(1-100000\)。消耗的时间如下：
运行代码如下：
#include"bits/stdc++.h"
#include<time.h>
using namespace std;
#define N 10086
int a[N];
int n;
int cnt=0;
int l,r;
int main(void) {
ios::sync_with_stdio(false);
cin>>l>>r;
clock_t start = clock();
for(int j=l; j<=r; ++j) {
memset(a,0,sizeof(a));
cnt=0;
// cin>>n;
for(int i=1; i<=sqrt(j); ++i) {
if(j%i==0) {
a[++cnt]=i;
if(j/i!=i) a[++cnt]=j/i;
}
}
for(int i=1; i<=cnt; ++i) cout<<a[i]<<" ";
cout<<"\n";
}
clock_t ends = clock();
cout<<"\n Running time: "<<(double)(ends - start)/ CLOCKS_PER_SEC;
return 0;
}