数论（素数判断；素数筛；最大公约数/最小公倍数；快速幂）

1. 数素数-PAT⼄级1013(素数判断模板)

素数判断模板：

题目来源：

题目内容：

代码实现：

2. 素数个数-洛⾕P3912(素数筛模板)

素数筛模板（筛选n以内的素数）:

题目来源：

题目内容：

代码实现：

3. [NOIP2001 普及组] 最⼤公约数和最⼩公倍数问题(模板)

最大公约数/最小公倍数模板：

题目来源：

题目内容：

代码实现：

4. 快速幂（去acwing上看快速幂的视频讲解，然后直接记模板, 矩阵快速幂暂时不管）

快速幂模板：

题目来源：

题目内容：

代码实现：

题目心得：

1. 数素数-PAT⼄级1013(素数判断模板)

素数判断模板：

int getprime(int x){if(x < 2) return 0;for(int i = 2; i * i <= x; i++){if(x % i == 0) return 0;}return 1;}

题目来源：

PTA | 程序设计类实验辅助教学平台

题目内容：

令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 PM 到 PN 的所有素数。

输入格式：

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：

输出从 PM 到 PN 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

代码实现：

#include <iostream>
#include <vector>
using namespace std;
int isprime(int x){if(x<2) return 0;for(int i=2;i*i<=x;i++){if(x%i==0) return 0;}return 1;
}
int main(){int m,n;cin>>m>>n;int k=0;int num=2;vector<int> res;//返回结果//这里采用while循环while(k<n){//这里为什么不加等号 //因为当k=n的时候  已经有了n个素数 if(isprime(num)){k++;if(k>=m) res.push_back(num);}num++;	} k=0; for(int i=0;i<res.size();i++){//k++;cout<<res[i];if(k%10==0) cout<<endl;else if(i!=res.size()-1) cout<<" ";		}	return 0;	
}

2. 素数个数-洛⾕P3912(素数筛模板)

素数筛模板（筛选n以内的素数）:

 #include<iostream>using namespace std;int a[100010];int main(){int n;cin>>n;//for(int i=2;i*i<=n;i++){for(int j=i*i;j<=n;j+=i){a[j]=1;}}//上⾯这个for循环就是素数筛模板，直接记忆就可以for(int i=2;i<n;i++)if(!a[i])cout<<i<<endl;return 0;}

题目来源：

PTA | 程序设计类实验辅助教学平台

题目内容：

让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<105)，请计算不超过N的满足猜想的素数对的个数。

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:

输出样例:

代码实现：

 #include<iostream>using namespace std;int a[100010];int main(){int n;cin>>n;//是素数数组值a[j]=0;for(int i=2;i*i<=n;i++){for(int j=i*i;j<=n;j+=i){a[j]=1;}}//上?这个for循环就是素数筛模板，直接记忆就可以int k=0;//素数对的个数for(int i=2;i<=n-2;i++){//注意一下：这里i是可以取到n的（a[n]存在) if(a[i]==0&&a[i+2]==0){k++; //cout<<i<<" "<<i+2<<endl;}} cout<<k;return 0;}

3. [NOIP2001 普及组] 最⼤公约数和最⼩公倍数问题(模板)

最大公约数/最小公倍数模板：

//最大公约数
int gcd(int x, int y){return y ? gcd(y, x % y):x;}
// 求最小公倍数
int lcm(int a, int b) {int gcdValue = gcd(a, b);return (a * b) / gcdValue;
}

题目来源：

PTA | 程序设计类实验辅助教学平台

题目内容：

本题要求编写程序，计算 2 个有理数的和、差、积、商。

输入格式：

输入在一行中按照 a1/b1 a2/b2 的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为 0。

输出格式：

分别在 4 行中按照 有理数1 运算符有理数2 = 结果 的格式顺序输出 2 个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式 k a/b，其中 k 是整数部分，a/b 是最简分数部分；若为负数，则须加括号；若除法分母为 0，则输出 Inf。题目保证正确的输出中没有超过整型范围的整数。

输入样例 1：

2/3 -4/2

输出样例 1：

2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

输入样例 2：

5/3 0/6

输出样例 2：

1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

代码实现：
来源：1034. 有理数四则运算(20)-PAT乙级真题 – liuchuo

#include <iostream>
#include <cmath>
using namespace std;
long long a, b, c, d;
long long gcd(long long t1, long long t2) {return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}
void func(long long m, long long n) {if (m * n == 0) {printf("%s", n == 0 ? "Inf" : "0");return ;}bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));m = abs(m); n = abs(n);long long x = m / n;printf("%s", flag ? "(-" : "");if (x != 0) printf("%lld", x);if (m % n == 0) {if(flag) printf(")");return ;}if (x != 0) printf(" ");m = m - x * n;long long t = gcd(m, n);m = m / t; n = n / t;printf("%lld/%lld%s", m, n, flag ? ")" : "");
}
int main() {scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);return 0;
}

题目心得：

abs（）；//绝对值函数开头引用： #include <cmath>

4. 快速幂（去acwing上看快速幂的视频讲解，然后直接记模板, 矩阵快速幂暂时不管）

快速幂模板：

 #include<iostream>using namespace std;int main(){int a,b,c;cin>>a>>b>>c;int res=1%c;//防⽌b为0的情况while(b){if(b&1)res=res*1ll*a%c;//因为这⾥res*a有可能数据溢出，所以将其转化为long longa=a*1ll*a%c;//因为这⾥a*a有可能溢出所以将其转化为longlongb>>=1;}cout<<res<<endl;}

题目来源：

AcWing - 算法基础课

题目内容：

给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi的值。

输入格式

第一行包含整数 n。

接下来 n行，每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 abiimodpi的值。

每个结果占一行。

数据范围

1≤n≤100000,1≤ai,bi,pi≤2×109

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

代码实现：

#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;LL qmi(int a,int b,int p){LL res=1%p;while(b){if(b&1)//如果b=1 res=res*a%p;a=a*(LL)a%p;//加上LL是为了防止溢出 b>>=1;//b转换成二进制，向右移一位 }return res;}int main(){int n;cin>>n;while(n--){int a,b,p;cin>>a>>b>>p;cout<<qmi(a,b,p)<<endl;}return 0;
}

题目心得：

说明一下：AcWing平台也是有格式要求的（只不过很少）
这道题后面输出的时候别忘了加上换行即可