<cmath>中常用函数
pow(base, exponent)
sqrt(x)
fmax、fmin、fabs
ceil、floor、round（四舍五入）
上述这些返回值和参数默认都是浮点数 注意强制类型转换 注意double强制转int 向下舍入
e.x. %的除数和被除数都必须为整型变量且除数不能为0否则runtime error
abs的返回值虽然是整型，但它同时为整型和浮点型重载，可替代fabs
fmin、fmax是<cmath>中求最值的方法，不过我们通常使用algorithm头文件中的min 、max，后者还可以自定义比较函数模运算
负数取模
e.x. 日期与当前日期的天数差值可能为负
(days % 7 + 7) % 7
加上求模的除数仍要再取一次模，保证原来模为0的情况仍为0大数求模
(a*b) % c = (a % c * b % c) % c
(a+b) % c = (a % c + b % c ) % c
- GCD & LCM
最大公约数 Greatest Common Divisor
欧几里得算法 辗转相除
while( b!= 0) {
int t = a % b;
a = b;
b = t;
}
return a;
// 一行
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
最小公倍数 Least Common Multiple
a * b / gcd(a,b)
- 素数
- 试除法素数判定
因子必定是成对出现的
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
- 素数筛法
1到n中期望意义上有个素数。
Sieve of Eratosthenes 排除法
O(n*log(log(n)))
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i; j <= n; j += i)
st[j] = true;
}
}
Sieve of Euler 欧拉筛法
O(n) 每个数只被它最小的质因子筛掉
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
- 分解质因数
试除法分解质因数
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
最后要多加一步x>1的判断，因为最多只有一个大于的质因子
试除法求所有约数
大小为a的数的期望的约数个数为个
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
求解幂次求和
普通做法O(n)
分治O(lgn)
- 数位拆解
do{
} while(a != 0);
可避免数本身为0时未分解到任何结果的情况 - 进制转换
- 注意字符与数字比较时一定记得加单引号'0'
- 注意向字符串转换和从字符串转换时的反序和反向遍历操作
- 注意处理0和负数
从字符串转换时判断s[0] == '-' ，向字符串转换时0和负数的构造
- 高精度
- 高精度加法
vector<int> bigAdd(vector<int>& a, vector<int>& b) {
vector<int> res;
int alen = (int)a.size();
int blen = (int)b.size();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= alen && i > blen) {
break;
}
if (i < alen) {
g += a[i];
}
if (i < blen) {
g += b[i];
}
res.push_back(g % BASE);
g /= BASE;
}
return res;
}
- 高精度乘法
vector<int> bigMul(vector<int>& a, vector<int>& b) {
int alen = (int)a.size();
int blen = (int)b.size();
int index;
for (index = 0; index < a.size() && a[index] == 0; index++) {}
if (index == a.size()) return { 0 };
for (index = 0; index < b.size() && b[index] == 0; index++) {}
if (index == b.size()) return { 0 };
vector<int> res(alen + blen, 0);
// i*j存放i+j
for (int i = 0; i < alen; i++) {
for (int j = 0; j < blen; j++) {
res[i + j] += a[i] * b[j];
}
}
int g = 0;
for (int i = 0; i < (int)res.size(); i++) {
int tmp = res[i] + g;
res[i] = tmp % BASE;
g = tmp / BASE;
}
while (res.back() == 0) {
res.pop_back();
}
return res;
}
- 高精度求模
- 快速幂
基于倍增的思想
求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
矩阵快速幂
mat qPow (mat A, ll n) {
int len = (int)A.size();
mat res(len, vector<BigInt>(len));
res[0][0] = res[1][1] = 1;
res[0][1] = res[1][0] = 0;
while (n) {
if ( n & 1 ) {
res = matrixMultiply(res, A);
}
A = matrixMultiply(A, A);
n >>= 1;
}
return res;
}
- 求组合数
Cnk mod p - k <= 2000 递推法
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
- k <= 10^5 逆元法 预处理
乘法逆元
- 定义
若整数b，m互质，并且b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为。
逆元可以避免数论中除法产生非整数的情况- 乘法逆元的特点
乘法逆元的应用
又根据 费马小定理
可得b存在乘法逆元的充要条件是b与模数m互质且当模数m为质数时，即为b的乘法逆元；而如果m不是质数，则求逆元只能用扩展欧几里得定理
应用
求组合数
组合数阶乘
-
k <= 10^18 p是质数 Lucas定理
欧拉函数
欧拉函数= 1到n中与n互质的n个数
欧拉定理
如果n是素数，
如果n是合数，,
推广费马小定理
如果n是任一整数且a与n互素
- 扩展欧几里得函数
如果d|a且d|b，则d|(a+b), d|(qa + pb)
裴蜀定理
有任意正整数a, b，gcd（a，b）=d，那么对于任意的整数x，y，ax+by都一定是d的倍数，特别地，一定存在整数x，y，使ax+by=d成立。
推论
a,b互素的充要条件是存在整数x，y使ax+by=1
- 高斯消元
O(n^3)
