算法
1.gcd与lcm（最大公约数与最小公倍数）
STL库函数中自带库函数__gcd(a,b),因此可以写出lcm的函数
typedef long long ll;
ll lcm(ll a,ll b) return a*b/__gcd(a,b);
2.lowbit函数
lowbit()可以快速求得 x 二进制表示中最低位 1 表示的值
int lowbit(int x)
return x&-x;
原理就是 ==x&-x== 二进制数的负数是正数取反加一
3.快速幂 ($${a^b}\ \% \ p$$)
typedef long long ll;
int q_mod(int a, int b, int p)
{
ll res = 1 % p;
while(b)
{
if(b & 1) res = res * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return res;
4.逆元（广义化的倒数）
乘法逆元定义：
若 整数b，m互质，且对于 任意的整数a，如果满足b|a（即b能整除a，a%b==0），则存在一个整数x，使得：a/b≡a*x(mod m)（即(a/b) mod m = a*x）则称 x 为 b的模m 乘法逆元，记为：b^(-1)(mod m)。（联想一下：除b等于乘b的负一次方）
费马小定理：
a ^ (p-1) ≡ 1 (mod p) （p为质数）。
int qmi(LL a, LL b) //当n为质数时，可以用快速幂求逆元
{
int res = 1;
while(b)
{
if(b & 1) res = res * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return res;
}
int divide(LL a, LL b)// 当n不是质数时，可以用扩展欧几里得算法求逆元
{
return a * qmi(b, MOD - 2) % MOD;
}
5.裴蜀定理
如果 a,b 均是正整数且互质，那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 ab−a−b。
6.树与图的存储
树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
void add(int a, int b) // 添加一条边a->b
{
//存下b的值，b下一个指向a的下个一节点，a的下一个节点指向b
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
深度优先遍历
时间复杂度O(n+m)，n表示点数，m表示边数
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
7.并查集
int p[N];
void init(int n) // 初始化 n是元素个数
{
for(int i = 0 ; i < n ; i++)
p[i]=i;
}
int find(int x) // 查找
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b) // 合并
{
p[find(a)] = find(b);
}
8.字符串处理
| 方法 | 解释 |
|---|---|
string replace (size_t pos, size_t len, const string& str); |
pos表示要替换的子串在原字符串中的起始位置，len表示要替换的子串的长度，str表示用来替换的字符串。 |
size_t find (const char* s, size_t pos, size_t n) |
s为要查找的字符数组；pos为查找的起始位置；n为要查找的字符个数 |
reverse(s.begin(),s.end()) |
algorithm库函数，完成字符串的翻转 |
9.树状数组
$$ c[x] = ( x - lowbit(x) , x]$$
10.KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i++)
{
while (j && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j++;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i++)
{
while (j && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j++;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
11.质因数分解
int n;
cin >> n;
for(int i = 2 ; i <= n/i ;i++)
{
if(n%i==0)
{
int cnt = 0;
while(n%i==0)
{
cnt++;
n/=i;
}
// 输出分解的质数和该质数的指数
cout << i <<" " << cnt <<endl;
}
}
if(n>1)
{
cout << n <<" "<<1<<endl;
}
