模板&复习

发表于

基础

把编辑器/编译器调到舒服的状态（见考试安排）
学会用批处理和写对拍（见批处理）
学会随机化生成（见随机化）
学会离散化（这种最方便）

1
2
3
4
5
6
7
8
for(int i=1;i<=n;++i){
	a[i]=ori[i]=io;
}
sort(ori+1,ori+n+1);
tot=unique(ori+1,ori+n+1)-ori-1;
for(int i=1;i<=n;++i){
	a[i]=lower_bound(ori+1,ori+tot+1,a[i])-ori;
}

掌握c风格输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
scanf：
int -> %d
long long -> %lld
unsigned int -> %u
unsigned long long -> %llu
float -> %f
double -> %lf
long double -> %Lf
char -> %c
char a[] -> %s
printf：
int -> %d
long long -> %lld
unsigned int -> %u
unsigned long long -> %llu
float -> %f
double -> %f （和scanf不一样！）
long double -> %Lf
char -> %c
char a[] -> %s

稳固代码风格：

1
2
3
4
5
6
7
8
9
++i
只有函数的大括号换行，其他不换行
用c风格输入输出
无论什么系统，使用快读
尽量用局部变量
规定范围的常量用对应变量的大写命名
主体在MAIN()中处理，在main()中做预处理，较长的函数要分段
部分分写在namespace里
所有函数加IL(inline)

附个模板：

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
int main()
{
	return 0;
}

分块&莫队

分块、莫队：暴力的加强版，思维难度小，代码量小，复杂度未必最优。（适合康复第一阶段训练）
（具体题目&代码见【学习笔记】分块&莫队）

图论

存图方式：
1、邻接矩阵
2、邻接表
nume=1为了方便找反向边，=-1则head要设为-1（小于0即可）

1
2
3
4
5
6
7
8
9
10
11
12
13
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M<<1];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
for(int i=head[x];i;i=e[i].nxt){
	int to=e[i].to;
	...
}

单元最短路径

（spfa它死了）
dijkstra：要求边权都是非负数
1、稠密图（m和n^2同级别），复杂度n^2
2、稀疏图，堆优化，复杂度(m+n)logm（注意到logm和logn同级别）
3、边权较小，桶优化，时间复杂度(m+n·最大边权），空间复杂度（n·最大边权+m）
对于不同的条件，使用不同的方法找最小边权。

dijk基于贪心，只要一个点被选中标记之后，任何其他路径不会使它更优即可使用。
spfa则是使图中的每条边都满足三角形不等式（不满足则存在不合题意的环），即对于边(x,y,z)，cal(dp[x],z)>dp[y]，其中cal代表某种运算。

堆优化dijk

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
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
77
78
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100000+8,M=200000+8;
int n,m,s;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M<<1];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
int dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII> >pq;
IL void dijk()
{	
	memset(dis,0x3f,sizeof(dis));
	//memset(vis,0,sizeof(vis));
	dis[s]=0;
	pq.push(mp(0,s));
	while(!pq.empty()){
		int x=pq.top().se;
		pq.pop();
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+e[i].f){
				dis[to]=dis[x]+e[i].f;
				pq.push(mp(dis[to],to)); 
			}
		}
	}
	for(int i=1;i<=n;++i){
		printf("%d ",dis[i]);
	}
}
int main()
{
	n=io;m=io;s=io;
	for(int i=1;i<=m;++i){
		x=io;y=io;z=io;
		add_edge(x,y,z);
		//add_edge(y,x,z);
	}
	dijk();
	return 0;
}

01bfs：边权为0或1的图求单源最短路
通过双端队列bfs，边权为0则从队头入队，边权为1从队尾入队。任意时刻保持队列的“两段性”和“单调性”
一个点最多入队两次，可以用vis判断（不用也是正确的）。复杂度n+m

luogu1948 [USACO08JAN]电话线Telephone Lines
二分答案后转化成01bfs

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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<deque>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=1000+8,P=10000+8;
int n,p,k;
int ori[P],tot;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[P<<1];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
deque<int> q;
int dis[N];
//bool vis[N];
IL bool ok(int mid)
{
	q.clear();
	memset(dis,0x3f,sizeof(dis));
	//memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.pb(1);
	while(!q.empty()){//每个值最多入队两次，+1和+0各入队一次 
		int x=q.front();
		q.pop_front();
		//if(vis[x])	continue;
		//vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+(e[i].f>mid)){
				dis[to]=dis[x]+(e[i].f>mid);
				if(e[i].f<=mid){
					q.push_front(to);
				}
				else{
					q.pb(to);
				}
			} 
		}
	}
	return dis[n]<=k;
}
IL void MAIN()
{
	int l=0,r=tot,mid=0,ans=tot+1;
	while(l<=r){
		mid=(l+r)>>1;
		if(ok(mid)){
			ans=mid;
			r=mid-1; 
		}
		else{
			l=mid+1;
		}
	}
	if(ans<=tot)	printf("%d",ori[ans]);
	else	printf("-1");
}
int main()
{
	n=io;p=io;k=io;
	for(int i=1;i<=p;++i){
		x=io;y=io;z=io;
		ori[i]=z;
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	sort(ori+1,ori+p+1);
	tot=unique(ori+1,ori+p+1)-ori-1;
	for(int i=2;i<=nume;++i){
		e[i].f=lower_bound(ori+1,ori+tot+1,e[i].f)-ori;
	}
	MAIN();
	return 0;
}

bzoj3073. [Pa2011]Journeys
线段树建图后转化成01bfs

线段树建图的步骤：（from lvzelong2014）
1、A树每个节点向父亲连边，B树每个节点向儿子连边。边权为零。
2、每个B树的叶子节点向对应的A树的叶子节点连边。
3、对于a~b连向c~d，在A树上找到a~b对应的区间u1,u2……un，将其连向虚拟节点p1，边权为0
4、虚拟节点p1到虚拟节点p2连上边权为1的边
5、在B树上找到c~d对应的区间v1,v2……vn从p2连到这些区间，边权为0

3-5的连边为(a,b)->(c,d)，(c,d)->(a,b)要再连一次。
也可以将p1,p2合并成一个点，然后将3或者5中边权改为1。
点或边的数组开小了 就和线段树开小了一样常见的错误

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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=500000+8,M=100000+8;
int n,m,p;
int a,b,c,d;
int numn;
int nume,head[N*8+M*2];
struct edge{
	int to,nxt,f;
}e[N*9+M*4*25];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
#define ls (t<<1)
#define rs (t<<1|1)
int tr1[N*4],tr2[N*4];
IL void add1(int t,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr){
		add_edge(tr1[t],numn,1);
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)	add1(ls,l,mid,ll,rr);
	if(mid<rr)	add1(rs,mid+1,r,ll,rr);
}	
IL void add2(int t,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr){
		add_edge(numn,tr2[t],0);
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)	add2(ls,l,mid,ll,rr);
	if(mid<rr)	add2(rs,mid+1,r,ll,rr);
}
IL void add()
{
	++numn;
	add1(1,1,n,a,b);
	add2(1,1,n,c,d);
	++numn;
	add1(1,1,n,c,d);
	add2(1,1,n,a,b);
}
int be[N],en[N];
IL void build1(int t,int l,int r)
{
	tr1[t]=++numn;
	if(l==r){
		be[l]=numn;
		return;
	}
	int mid=(l+r)>>1;
	build1(ls,l,mid);
	build1(rs,mid+1,r);
	add_edge(tr1[ls],tr1[t],0);
	add_edge(tr1[rs],tr1[t],0);
}
IL void build2(int t,int l,int r)
{
	tr2[t]=++numn;
	if(l==r){
		en[l]=numn;
		return;
	}
	int mid=(l+r)>>1;
	build2(ls,l,mid);
	build2(rs,mid+1,r);
	add_edge(tr2[t],tr2[ls],0);
	add_edge(tr2[t],tr2[rs],0);
}
IL void init()
{
	build1(1,1,n);
	build2(1,1,n);
	for(int i=1;i<=n;++i){
		add_edge(en[i],be[i],0);//
	}
}
int dis[N*8+M*2];
deque<int> q;
IL void bfs01()
{
	memset(dis,0x3f,sizeof(dis));
	dis[be[p]]=0;
	q.pb(be[p]);
	while(!q.empty()){
		int x=q.front();
		q.pop_front();
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+e[i].f){
				dis[to]=dis[x]+e[i].f;
				if(e[i].f)	q.pb(to);
				else	q.push_front(to);
			}		
		}
	}
	for(int i=1;i<=n;++i){
		//if(i!=p)	printf("%d\n",dis[en[i]]);
		//else	printf("0\n");
		printf("%d\n",dis[be[i]]);
	}
}
int main()
{
	n=io;m=io;p=io;
	init();
	for(int i=1;i<=m;++i){
		a=io;b=io;c=io;d=io;
		add();
	}
	bfs01();
	return 0;
}

手写队列：
1、普通队列 he=1,ta=0;q[++ta]=x;while(he<=ta){…}
2、循环队列 he=1,ta=1;q[ta++]=x;while(he!=ta){…}

luogu3008 [USACO11JAN]道路和飞机Roads and Planes
缩点+拓扑+dijk

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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=25000+8,M=50000+8;
int n,r,p,s;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M*3];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
int num,bl[N];
vector<int> v[N];
IL void dfs(int x)
{
	bl[x]=num;
	v[num].pb(x);
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(!bl[to]){
			dfs(to);
		}
	}
}
int ind[N];
int q[N],he,ta;
int dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII> > pq; 
IL void solve(int t)
{
	while(!pq.empty())	pq.pop();
	for(int i=0;i<v[t].size();++i){
		pq.push(mp(dis[v[t][i]],v[t][i])); 
	}
	while(!pq.empty()){
		int x=pq.top().second;
		pq.pop();
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+e[i].f){
				dis[to]=dis[x]+e[i].f;
				if(bl[to]==bl[x]){
					pq.push(mp(dis[to],to));
				}
			}
			if(bl[to]!=bl[x]){
				--ind[bl[to]];
				if(!ind[bl[to]])	q[++ta]=bl[to];
			}	
		}
	}
}
IL void MAIN()
{
	he=1;ta=0;
	if(ind[bl[s]])	q[++ta]=bl[s];
	for(int i=1;i<=num;++i){
		if(!ind[i])	q[++ta]=i;
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	while(he<=ta){
		int x=q[he];
		++he;
		solve(x);
	}
	for(int i=1;i<=n;++i){
		if(dis[i]>5e8)	printf("NO PATH\n");//不能用if(dis[i]==0x3f3f3f3f)，因为存在负边权 
		else	printf("%d\n",dis[i]);
	}
}
int main()
{
	n=io;r=io;p=io;s=io;
	for(int i=1;i<=r;++i){
		x=io;y=io;z=io;
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	for(int i=1;i<=n;++i){
		if(!bl[i]){
			++num;
			dfs(i);
		}
	}	
	for(int i=1;i<=p;++i){
		x=io;y=io;z=io;
		++ind[bl[y]];
		add_edge(x,y,z);
	}
	MAIN();
	return 0;
}

任意两点间最短路

dijk n^3或nmlogm
floyd n^3（还可以用于解决传递闭包）

最大流

dinic

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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=10000+8,M=100000+8;
int n,m,s,t;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M*2];
IL void add_edge_2(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
	e[++nume]=(edge){x,head[y],0};head[y]=nume;
}
int cur[N];
int dis[N];
int q[N],he,ta;
IL int dfs(int x,int low)
{
	if(x==t||!low)	return low;
	int flow=0,tmp=0;
	for(int &i=cur[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(dis[to]==dis[x]+1&&(tmp=dfs(to,min(low,e[i].f)))){
			flow+=tmp;
			low-=tmp;
			e[i].f-=tmp;
			e[i^1].f+=tmp;
			if(!low)	return flow;
		}
	}
	if(low)	dis[x]=0;
	return flow;
}
IL bool bfs()
{
	memset(dis,0,sizeof(dis));
	he=1;ta=0;
	q[++ta]=s;
	dis[s]=1;
	while(he<=ta){
		int x=q[he];
		++he;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(!dis[to]&&e[i].f){
				dis[to]=dis[x]+1;
				q[++ta]=to;
				if(to==t)	return 1;
			}
		}
	}
	return 0;
}
IL void dinic()
{
	int maxflow=0;
	while(bfs()){
		for(int i=1;i<=n;++i)	cur[i]=head[i];
		maxflow+=dfs(s,INT_MAX);
	}
	printf("%d",maxflow);
}
int main()
{
	n=io;m=io;s=io;t=io;
	for(int i=1;i<=m;++i){
		x=io;y=io;z=io;
		add_edge_2(x,y,z);
	}
	dinic();
	return 0;
}

数论

线性筛

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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=10000000+8;
int n,qn;
int min_p[N],pri[N],num;
int main()
{
	n=io;qn=io;
	for(int i=2;i<=n;++i){
		if(!min_p[i]){
			min_p[i]=i;
			pri[++num]=i;
		}
		for(int j=1;j<=num&&pri[j]<=min_p[i]&&pri[j]<=n/i;++j){
			min_p[pri[j]*i]=pri[j];
		}
	}
	while(qn--){
		int x=io;
		printf(min_p[x]==x?"Yes\n":"No\n");
	}
	return 0;
}

快速幂

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
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
LL a,b,mod;
IL LL ksm(LL a,LL b)
{
	LL tmp=1%mod;
	while(b){
		if(b&1)	tmp=tmp*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return tmp;
}
int main()
{
	a=io;b=io;mod=io;
	printf("%lld^%lld mod %lld=%lld",a,b,mod,ksm(a,b));
	return 0;
}

luogu2568 GCD
所求为sum{prime}sum(2*sum(phi[i])(i=1 to n/prime)-1)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=10000000+8;
int n;
int phi[N],min_p[N],pri[N],num;
LL sum[N],ans;
int main()
{
	n=io;
	phi[1]=1;
	sum[1]=1;
	for(int i=2;i<=n;++i){
		if(!min_p[i]){
			min_p[i]=i;
			pri[++num]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=num&&pri[j]<=min_p[i]&&pri[j]<=n/i;++j){
			min_p[i*pri[j]]=pri[j];
			phi[i*pri[j]]=phi[i]*(i%pri[j]?pri[j]-1:pri[j]);
		}
		sum[i]=sum[i-1]+phi[i];
	}
	for(int i=1;i<=num;++i){
		ans+=sum[n/pri[i]]*2-1;
	}
	printf("%lld",ans);
	return 0;
}