（持续更新）
递归与递推
概念
递归：从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。
递推：递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算机前面的一些项来得出序列中的指定象的值。
递归与递推区别：相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。
例题
题目描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1 ~ 9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入
从标准输入读入一个正整数N (N< 10001000)
输出
程序输出该数字用数码1 ~ 9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入
100
样例输出
111
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
int num[10];
int sum;
int getsum(int a, int b) //求得num[a] - num[b]所组成的整数
{
int re = 0;
for(int i = a; i<= b; i++)
re = re * 10 + num[i];
return re;
}
void solve(int n)
{
for(int i = 1; i < 10; i++)
{
int a = getsum(1, i);
if(a >= n) return ;
for(int j = i + (9 - i)/2; j < 10; j++)
{
int b = getsum(i + 1, j);
int c = getsum(j + 1, 9);
if(b > c && c && b % c == 0 && b / c == n - a)
sum++;
}
}
}
int main()
{
int n;
cin>>n;
for(int i = 1; i < 10; i++)
num[i] = i;
do
{
solve(n);
}while(next_permutation(num + 1, num + 10));
cout<<sum;
return 0;
}
题目描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是： oo oooo
如果同时翻转左边的两个硬币，则变为：oooo oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入
两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度< 1000
输出
一个整数，表示最小操作步数。
样例输入
*o o o**
o** o o*
样例输出
11
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
string s1,s2;
int p1[1005],p2[1005];
int ans=0;
int main()
{
cin>>s1>>s2;
//输入数据处理
for(int i=0 ;i<s1.length(); i++)
{
if(s1[i]=='*')p1[i]=1;
if(s1[i]=='o')p1[i]=-1;
if(s2[i]=='*')p2[i]=1;
if(s2[i]=='o')p2[i]=-1;
}
//进行翻转操作
for(int i=0 ;i<s1.length()-1 ;i++)
{
if(p1[i]!=p2[i])
{
ans++;
p1[i] = -p1[i];
p1[i+1] = -p1[i+1];
}
}
cout<<ans<<endl;
return 0;
}
Time Limit: 1000 ms
Memory Limit: 256 mb
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
输入输出格式
输入描述:
输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。
输出描述:
一个数据，是最少的旋转次数。
输入输出样例
输入样例:
4
4 3 2 1
输出样例:
6
思路：
实则为交换排序问题，采用冒泡排序即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
int main()
{
int N, ans = 0;
cin >> N;
int* a = new int[N];
for (int i = 0; i < N; i++)
cin >> a[i];
for (int i = 0; i < N-1; i++)
{
for (int j = 0; j < N-i-1; j++)
{
if (a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
ans++;
}
}
}
cout << ans << endl;
return 0;
}
二分和前缀和
概念
二分就是断确定边界的过程，二分一定有解所以当二分到无法再分时的那个元素就是解，即l=r指向的值。
二分不一定要有单调性，二分的本质是寻找某种性质的分界点。只要可以找到某种性质，使得区间的前半部分满足，后半部分不满足，那么就可以用二分把这个分界点找到。
前缀和预处理求出s[1~n]，然后就能快速求出任意数组任意区间里一段数的和，如求l ~ r区间的和，就是s[r]-s[l-1]，数组要从1开始从，s[0]=0，这样比如算s[1]-s[9]，就可以用s[9]-s[0],而s[0]其实就是0，没有元素，避免越界
S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]
例题
题目描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
6 5
5 6
样例输出
2问题描述1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
int main()
{
int n, k;
int h[100000];
int w[100000];
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> h[i] >> w[i];
}
int r = 100001;
int l=1;
int ans=0;
//二分查找，查找最接近k的分割长度len，即mid。
while (l<=r)
{
int mid=(l+r)/2;
int cnt = 0;
//累计可以切多少块
for (int i = 0; i < n; ++i)
{
cnt += (h[i] / mid) * (w[i] / mid);
}
if (cnt >= k)
{
l=mid+1;
ans=mid;
}else
{
r=mid-1;
}
}
cout<<ans<<endl;
return 0;
}
给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出格式
输出一个整数，代表K倍区间的数目。
样例输入
5 2
1
2
3
4
5
样例输出
61
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
long long input[100010],show[100010];
int main()
{
int n,k,tp;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>tp;
input[i]=(input[i-1]+tp)%k;
show[input[i]]++;
}
long long ans=0;
for(int i=0;i<k;i++) //0<i<k 因为mod k之后最大是k-1
ans+=show[i]*(show[i]-1)/2;
cout<<ans+show[0];
return 0;
}栈和队列
概念
由于大二上学期数据结构已学习，故略去，资料可参考书籍与ppt
例题
题目描述
给定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i。
小蓝将对这个序列进行 m 次操作，每次可能是将 a1, a2, · · · , aqi 降序排列，或者将 aqi , aqi+1, · · · , an 升序排列。
请求出操作完成后的序列。
输入
输入的第一行包含两个整数 n, m，分别表示序列的长度和操作次数。
接下来 m 行描述对序列的操作，其中第 i 行包含两个整数 pi, qi 表示操作类型和参数。当 pi = 0 时，表示将 a1, a2, · · · , aqi 降序排列；当 pi = 1 时，表示将 aqi , aqi+1, · · · , an 升序排列。
输出
输出一行，包含 n 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。
样例输入
3 3
0 3
1 2
0 2
样例输出
3 1 21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
const int N = 100005;
pair<int,int> s[N];
int ret[N];
int n,m;
int main()
{
cin>>n>>m;
int top=0;
int k=n;
for(int i=0;i<m;i++)
{
int p,q;
cin>>p>>q;
//0 是 1->q降序排列
if(!p)
{
while(top&&s[top].first==0)
q=max(q,s[top--].second);
while(top>=2&&s[top-1].second<=q)
top-=2;
s[++top]={0,q};
}
else if(top)
{
while(top&&s[top].first==1)
q=min(q,s[top--].second);
while(top>=2&&s[top-1].second>=q)
top-=2;
s[++top]={1,q};
}
}
int l=1,r=n;
for(int i=1;i<=top;i++)
{
if(s[i].first==0)
while(l<=r&&r>s[i].second)
ret[r--]=k--;
else
while(l<=r&&l<s[i].second)
ret[l++]=k--;
if(l>r)
break;
}
if(top%2)
while(l<=r)
ret[l++]=k--;
else
while(l<=r)
ret[r--]=k--;
for(int i=1;i<=n;i++)
cout<<ret[i]<<" ";
return 0;
}
题目描述
小的时候，你玩过纸牌游戏吗？
有一种叫做“拉马车”的游戏，规则很简单，却很吸引小朋友。
其规则简述如下：
假设参加游戏的小朋友是A和B，游戏开始的时候，他们得到的随机的纸牌序列如下：
A方：[K, 8, X, K, A, 2, A, 9, 5, A]
B方：[2, 7, K, 5, J, 5, Q, 6, K, 4]
其中的X表示“10”，我们忽略了纸牌的花色。
从A方开始，A、B双方轮流出牌。
当到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。
此例中，游戏过程：
A出K，B出2，A出8，B出7，A出X，此时桌上的序列为：
K,2,8,7,X
当轮到B出牌时，他的牌K与桌上的纸牌序列中的K相同，则把包括K在内的以及两个K之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。
此时，A、B双方的手里牌为：
A方：[K, A, 2, A, 9, 5, A]
B方：[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]
赢牌的一方继续出牌。也就是B接着出5，A出K，B出J，A出A，B出5，又赢牌了。
5,K,J,A,5
此时双方手里牌：
A方：[2, A, 9, 5, A]
B方：[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]
注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。
当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。
对于本例的初始手牌情况下，最后A会输掉，而B最后的手里牌为：
9K2A62KAX58K57KJ5
本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出-1。
输入
输入为2行，2个串，分别表示A、B双方初始手里的牌序列。
我们约定，输入的串的长度不超过30
输出
输出为1行，1个串，表示A先出牌，最后赢的一方手里的牌序。
样例输入
96J5A898QA
6278A7Q973
样例输出
2J9A7QA6Q68899771
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//#include <stdio.h>
//#include <cstdlib>
using namespace std;
string str1, str2, str3;
int k1 = 1, k2 = 1;
int main()
{
cin >> str1 >> str2;
while (str1.length() != 0 && str2.length() != 0)
{
// B赢了则跳过A，B继续出牌
if (k2)
{
// 如果str3中有与之相等的牌则进入
if (str3.find(str1[0]) != str3.npos)
{
k1 = 0;
str1 += str1[0]; // 末尾加上将要打出的牌
for (int i = str3.length() - 1; i > -1; i--)
{
str1 += str3[i]; // 末尾加牌
if (str3[i] == str1[0]) // 遇到相等的牌
{
// st3中删除并退出循环
str3.erase(i, 1);
break;
}
str3.erase(i, 1);
}
}
else
{
str3 += str1[0]; //桌面牌
}
str1.erase(0, 1); // 清除首位
}
k2 = 1;
if (str1.length() == 0) break;
// A赢了则跳过B，A继续出牌
if (k1)
{
// 如果str3中有与之相等的牌则进入
if (str3.find(str2[0]) != str3.npos)
{
k2 = 0;
str2 += str2[0]; // 末尾加上将要打出的牌
for (int i = str3.length() - 1; i > -1; i--)
{
str2 += str3[i]; // 末尾加牌
if (str3[i] == str2[0]) // 遇到相等的牌
{
// st3中删除并退出循环
str3.erase(i, 1);
break;
}
str3.erase(i, 1);
}
}
else
{
str3 += str2[0]; //桌面牌
}
str2.erase(0, 1); // 清除首位
}
k1 = 1;
}
if (str1.length() != 0) cout << str1;
else cout << str2;
return 0;
}
并查集和kmp
概念
并查集
初始化将每个节点包装成一个个集合，每个集合中存放这个元素并使其父节点指向自己。建立三个数据结构。
1.v → Element 表示集合的节点类，将原始输入元素包装成集合的类节点。
2.Element → Element 一个将每个节点指向父节点的映射
3.Element → size 这个Element指一个集合中，获得所有节点的祖先节点，他的父节点就是自己，作为一个集合的代表节点，并将其映射到集合的规模。
并查集的相关操作
查找代表节点findheap：对于一个集合中每一个节点，可以通过数据结构2寻找父节点，并不断往上遍历寻找。直到找到唯一的最顶层的祖先节点，此节点的父节点指向自己，就是一个集合的代表节点。
集合合并union：对于两个集合，获得他们的代表节点。在数据结构3，获得各自的size，将size进行比较。对规模较小的集合，把其代表节点的父节点由指向自己变为指向规模较大的代表节点，这样就形成了一个新的集合，代表节点为原规模较大的集合的代表节点。
查询find，判断两个节点是否属于一个集合：参考findheap过程，只需对两个节点findheap，得到各自代表节点，代表节点若是同一个，则为同一个节点。
kmp算法
从一个字符串中寻找连续子串的问题，令str为主串，k为寻找的部分
算法很经典，大二上学期数据结构已学习，故不再赘述
例题
题目描述
给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组
输入
第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· ,AN
对于 80% 的评测用例，1 ≤ N ≤ 10000。
对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。
输出
输出N个整数，依次是最终的A1,A2,··· ,AN。
样例输入
5
2 1 1 3 4
样例输出
2 1 3 4 51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
const int MAXN = 1e6 + 5;
int f[MAXN];
int a[MAXN];
int Find(int x)
{
if(f[x] == x)
{
return x;
}
else
{
f[x] = Find(f[x]);
return f[x];
}
}
// return f[x] == x ? x : (f[x] = Find(f[x]))
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <=MAXN;i++)
{ //初始化
f[i] = i;
}
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i] = Find(a[i]);
f[a[i]] = Find(a[i]+1);
}
for(int i = 1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
题目描述
w星球的一个种植园，被分成 m n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（ 1< m, n < 1000）。
接下来一行，一个整数k，表示下面还有k行数据(0 < k < 100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
输出
多少株
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 10051005;
int m,n,k,pre[maxn],ans;
bool vis[maxn];
void init()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n*m;i++)
pre[i] = i;
}
int find(int x)
{
if(x!=pre[x])
return pre[x] = find(pre[x]);
return x;
}
void join(int x,int y)
{
int xx = find(x);
int yy = find(y);
if(xx!=yy)
{
pre[yy] = xx;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=0;i<k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
join(x,y);
}
for(int i=1;i<=n*m;i++)
{
vis[find(i)] = 1;
// cout<<pre[i]<<" "<<find(i)<<endl;
}
for(int i=1;i<=n*m;i++)
ans += vis[i];
cout<<ans<<endl;
return 0;
}
最小生成树与最短路径
概念
最小生成树
一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。
最短路径
对于网图而言，最短路径就是两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，第二个顶点是终点。而非网图可以理解为所有边的权值都为1的网。
例题
题目描述
有n块芯片，有好有坏，已知好芯片比坏芯片多。
每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
给出所有芯片的测试结果，问哪些芯片是好芯片。
输入
输入数据第一行为一个整数n，表示芯片个数。
第二行到第n+1行为nn的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。
（2≤n≤20）
输出
按从小到大的顺序输出所有好芯片的编号
样例输入
3
1 0 1
0 1 0
1 0 1
*样例输出
1 31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main()
{
int n;
scanf("%d",&n);
int num[30][30];
for(int i=0;i<n;i++)
{//输入
for(int j=0;j<n;j++)
{
scanf("%d",&num[i][j]);
}
}
int sum[n];
for(int i=0;i<n;i++)
{//第i快测试第j块 j的结果
for(int j=0;j<n;j++)
{
if(i!=j&&num[i][j]==1)
{
sum[j]++;
}
}
}
for(int i=0;i<n;i++)
{//如果概率大于等于一半就满足条件
if(sum[i]>=n/2)
{
printf("%d ",i+1);
}
}
return 0;
}
质数与快速幂
概念
思想：每一步都把指数分成两半，而相应的底数做平方运算。不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
原理：(a b) % m = ((a % m) (b % m)) % m1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
typedef long long ll;
ll Pow1(ll my_base, ll my_exp)
{
ll ans = 1;
for (int i = 1; i <= my_exp; i++) ans *= my_base;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); //断开同步流
ll my_base, my_exp, result;
clock_t my_start, my_end;
cin >> my_base >> my_exp;
my_start = clock();
//该函数返回值是硬件滴答数
result = Pow1(my_base, my_exp);
cout << my_base << "^" << my_exp << "=" << result << endl;
my_end = clock();
cout << "time=" << ((double)my_end - my_start) / CLK_TCK << "s" << endl;
//要换算成秒，需要除以CLK_TCK或者 CLK_TCKCLOCKS_PER_SEC
return 0;
}
扩展欧几里得与高斯消元
概念
同余
两个整数a和b及模m，如果a%m=b%m，称a和b对m同余。同余也可以理解为a−b是m的倍数:m∣( a−b )，例如6∣(23 −11)，23和11对模6同余。
同余符号计为a≡b(mod m)。
逆元
给出a和m，求解ax≡1(mod m)，即ax除m的余数是1。那么该方程的一个解x称为a模m的逆元，注意这样的x有很多，都称为逆。
逆元与除法取模
逆元一重要作用就是求除法的模，首先我们看一下模运算：
加：(a+b)%m=(a%m+b%m)%m
减：(a−b)%m=(a%m−b%m)%m
乘：(a∗b)%m=(a%m∗b%m)%m
除：(a/b)%m≠(a%m/b%m)%m
对于除法可以用逆元求解
设b的逆元是k，则：
（a/b)%m=(a/b%m)(bk%m)=(a/b)bk%m=ak%m
即(a/b)%m=(ak)%m
费马小定理
假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
素数筛
枚举所有小于数，看是否它能整除其他自然数，但实际上只需要枚举根号次。
欧拉函数
就是对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。
欧拉函数的通式：φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)……(1-1/pn)
其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
欧拉函数的一些性质：
① 当m,n互质时，有phi（mn）= phi（m）phi（n）；
② 若i%p==0，有phi（ip） = p phi(i)；
③ 对于互质x与p，有x^phi§≡1（mod p),因此x的逆元为x^(phi§-1)，即欧拉定理。
（特别地，当p为质数时，phi（p）=p-1,此时逆元为x^(p-2)，即费马小定理）
④ 当n为奇数时，phi(2n)=phi(n)
⑤ 若x与p互质，则p-x也与p互质，因此小于p且与p互质的数之和为phi(x)x/2;
⑥N>1，不大于N且和N互素的所有正整数的和是 1/2 N eular(N)。
⑦若(N%a == 0 && (N/a)%a==0) 则有:E(N)=E(N/a)a;
⑧若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
欧拉定理
若gcd(a,p)=1,则a^φ(p) ≡ 1 (mod p) 这个定理可以求乘法逆元（乘法逆元讲解）。
而且包含了费马小定理（a ^ (p-1) ≡ 1 (mod p)要求p为质数），因为当p为质数时φ(p) = p-1。
背包问题
1 |
|
常用代码模板——基础算法
1 | //快速排序 |
1 | //归并排序 |
1 | //整数二分算法 |
1 | //浮点数二分算法 |
1 | //高精度加法 |
1 | //高精度减法 |
1 | //高精度乘低精度 |
1 | //高精度除以低精度 |
1 | //二维前缀和 |
1 | //二位差分 |
1 | //位运算 |
1 | //双指针算法 |
1 | //离散化 |
1 | //区间合并 |