复习整理：数学知识
数及其运算
自然数、整数、有理数、实数及其算术运算
难度过低，一笔带过。
进制转换
n转化为b进制数核心代码
int x = 0;
while(n != 0){
a[x] = n%b;
x++;
n = n/b;
}初等数论
整除、因倍质合、指数
“
剩下过于简单，一笔带过。
取整
- 下取整：
\lfloor x \rfloor ，C++中的floor函数。 - 上取整：
\lceil x \rceil ，C++中的ceil函数。
模运算、同余
- 模运算： 取余
- 同余：
a 和b 除以m 的余数相同，即a \equiv b \pmod m
同余的性质：
- 自反性：
a \equiv a \pmod m 。 - 对称性：若
a\equiv b\pmod m ，则b\equiv a\pmod m 。 - 传递性：若
a\equiv b\pmod m ，b\equiv c\pmod m ，则a\equiv c\pmod m 。 - 可加性：
a\pm c\equiv b\pm d\pmod m 。 - 可乘性：
ac\equiv bd\pmod m 。 - 对于任意自然数
n ，如果a\equiv b\pmod m ，则an\equiv bn\pmod m 。 - 如果
ac\equiv bc\pmod m ，\gcd(c,m) = 1 ，则a\equiv b\pmod m 。
整数唯一分解定理（算数基本定理）
设正整数 a，那么必有表示：
其中
int p[105],a[105],tot=0;
void getfac(){
for(int i = 2; i*i <= x; i++){
if(x%i == 0){
p[++tot] = i;
while(x%i == 0){
a[tot]++;
x /= i;
}
}
}
if(x > 1){
p[++tot] = x;
a[tot] = 1;
}
}碾转相除
int gcd(int a,int b){
if(b == 0){
return a;
}
return gcd(b,a%b);
}素数筛法
Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法） ，时间复杂度是
const int MAXN = 1e5+5;
int prime[MAXN],cnt;
bool flag[MAXN];
void E_Sieve(){
for(int i = 2; i <= n; i++){
if(!flag[i]){
for(int j = 2; j * i <= n; j++){
flag[j * i] = 1;
}
}
}
for(int i = 2; i <= n; i++){
if(!flag[i]){
prime[++cnt] = i;
}
}
}