板子A（扩展欧几里得）
题目描述
求关于x的同余方程 ax≡1(modb) 的最小正整数解。
输入格式
一行，包含两个正整数 a,b，用一个空格隔开。
输出格式
一个正整数 x，即最小正整数解。输入数据保证一定有解。
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 long long xx,yy;
6 void exgcd(long long aa,long long bb)
7 {
8 if(bb==0)
9 {
10 xx=1;
11 yy=0;
12 return;
13 }
14 exgcd(bb,aa%bb);
15 long long tt=yy;
16 yy=xx-(aa/bb)*yy;
17 xx=tt;
18 }
19 int main()
20 {
21 long long aa,bb;
22 scanf("%lld%lld",&aa,&bb);
23 exgcd(aa,bb);
24 xx=((xx%bb)+bb)%bb;
25 printf("%lld",xx);
26 return 0;
27 }
板子B1（乘法逆元（费马小定理或欧拉定理））
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入格式
一行n,p
输出格式
n行,第i行表示i在模p意义下的逆元。
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 long long mod;
6 long long ksm(long long aa,long long bb)
7 {
8 long long ret=1;
9 while(bb!=0)
10 {
11 if(bb%2==1)ret=((ret%mod)*(aa%mod))%mod;
12 bb/=2;
13 aa=(aa%mod)*(aa%mod)%mod;
14 }
15 return ret%mod;
16 }
17 int main()
18 {
19 long long i;
20 long long n;
21 scanf("%lld%lld",&n,&mod);
22 for(i=1;i<=n;i++)
23 {
24 printf("%lld\n",ksm(i,mod-2));
25 }
26 return 0;
27 }
板子B2（乘法逆元（扩展欧几里得））
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入格式
一行n,p
输出格式
n行,第i行表示i在模p意义下的逆元。
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 long long n,mod;
6 long long xx,yy;
7 void exgcd(long long aa,long long bb)
8 {
9 if(bb==0)
10 {
11 xx=1;
12 yy=0;
13 return;
14 }
15 exgcd(bb,aa%bb);
16 long long tt=yy;
17 yy=xx-(aa/bb)*yy;
18 xx=tt;
19 }
20 int main()
21 {
22 long long i;
23 scanf("%lld%lld",&n,&mod);
24 for(i=1;i<=n;i++)
25 {
26 exgcd(i,mod);
27 xx=((xx%mod)+mod)%mod;
28 printf("%lld\n",xx);
29 }
30 return 0;
31 }
板子B3（乘法逆元（线性筛））
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入格式
一行n,p
输出格式
n行,第i行表示i在模p意义下的逆元。
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 long long inv[3000100];
6 long long n,mod;
7 int main()
8 {
9 scanf("%lld%lld",&n,&mod);
10 long long i;
11 inv[1]=1;
12 printf("1\n");
13 for(i=2;i<=n;i++)
14 {
15 inv[i]=mod-(mod/i)*inv[mod%i]%mod;
16 printf("%lld\n",inv[i]);
17 }
18 return 0;
19 }
板子C（线性筛质数）
题目描述
如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）
输入格式
第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。
输出格式
输出包含M行，每行为Yes或No，即依次为每一个询问的结果。
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 bool vist[10000100];
6 int prim[1000010];
7 int tot=0;
8 int main()
9 {
10 int n,m;
11 int i,j;
12 scanf("%d%d",&n,&m);
13 for(i=2;i<=n;i++)
14 {
15 if(!vist[i])prim[++tot]=i;
16 for(j=1;j<=tot&&i*prim[j]<=n;j++)
17 {
18 vist[prim[j]*i]=1;
19 if(i%prim[j]==0)
20 break;
21 }
22 }
23 int qq;
24 vist[1]=1;
25 for(i=1;i<=m;i++)
26 {
27 scanf("%d",&qq);
28 if(vist[qq]==0)printf("Yes\n");
29 else printf("No\n");
30 }
31 return 0;
32 }
板子D（GCD&LCM）
题目描述
输入两个正整数m和n，求其最大公约数和最小公倍数。
输入格式
两个整数m和n。
输出格式
两个整数最大公约数，最小公倍数
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 using namespace std;
5 long long gcd(long long aa,long long bb)
6 {
7 if(bb==0)return aa;
8 else return gcd(bb,aa%bb);
9 }
10 int main()
11 {
12 long long n,m;
13 scanf("%lld%lld",&n,&m);
14 long long ls=gcd(n,m);
15 printf("%lld %lld",ls,n*m/ls);
16 return 0;
17 }