GESP-C++五级 题库
找出自然数 n 以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中线性筛法效率更高。
常见的质数筛有埃氏筛和欧拉筛(线性筛法),其中埃氏筛的时间复杂度为O(nlogn),经过一定的优化,可以到O(nloglogn),欧拉筛的时间复杂度为O(n),大部分情况下,欧拉筛的效率更高。
唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。
任何一个大于等于2的整数,都可以唯一的分解为若干个质数的幂次方的乘积的形式
找出自然数n以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。
埃氏筛法是一种简单直观的质数筛选算法,适用于较小范围内的质数查找,随着 n 的增大,其效率会下降,因为需要标记的倍数越多。线性筛法是在埃氏筛法基础上的改进,效率更高。
唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。
一个整数可以有多种因数分解的方式(比如顺序不同),但其包含的质数因子及其指数是唯一确定的。
相等序列
时间限制: 1.0 s
内存限制:512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · · ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作:
选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai * P ,P 为任意质数;
选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai /P ,P 为任意质数,要求Ai能被p整除。
小 A 想请你帮他计算出令序列中所有整数都相同 ,最少需要花费多少金币。
输入格式
第一行一个正整数N ,含义如题面所⽰ 。
第二行包含 N 个正整数 A1 , A2 , · … ,AN ,代表序列 A。
输出格式
输出一行 ,代表最少需要花费的金币数量。
输入样例
输出样例
数据范围
对于60%的测试点 ,保证 1 ≤ N, Ai ≤ 100 。
对于所有测试点 ,保证 1 ≤ N, Ai ≤ 105 。
#include <iostream>
using namespace std;
const int N = 100010;
int num[N][20];
int n, a[N];
void calc_prime_factor(int x)
{
for (int i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
int cnt = 0;
while (x % i == 0)
{
x /= i;
cnt++;
}
num[i][cnt]++;
}
}
if (x > 1)
{
num[x][1]++;
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
calc_prime_factor(a[i]);
}
long long ans = 0;
for (int i = 2; i < 100001; i++)
{
int pos = 0;
for (int j = 0; j < 20; j++)
{
pos += num[i][j];
}
num[i][0] = n - pos;
int median_exponent = 0;
pos = 0;
for (int j = 0; j < 20; j++)
{
pos += num[i][j];
if (pos * 2 >= n)
{
median_exponent = j;
break;
}
}
for (int j = 0; j < 20; j++)
{
ans += num[i][j] * abs(j - median_exponent);
}
}
printf("%lld\n", ans);
return 0;
}原根判断
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 知道,对于质数 p 而言,p 的原根 g 是满足以下条件的正整数:
其中 a mod p 表示 a 除以 p 的余数。
小 A 现在有一个整数 T,请你帮他判断 a 是不是 p 的原根。
【输入描述】
第一行,一个正整数 T,表示测试数据组数。
每组测试数据包含一行,两个正整数 a、p。
【输出描述】
对于每组测试数据,输出一行,如果 a 是 p 的原根则输出 Yes ,否则输出 No 。
【样例输入1】
【样例输出1】
【数据范围】
对于 40% 的测试点,保证 3<=p<=1000。
对于所有测试点,保证 1<=T<=20, 3<=p<=10^9,1<a<p , p为质数。
对于所有测试点,保证 ,-100<= A(i,j) <=100 。
#include <cstdio>
using namespace std;
int a, p;
int ans;
int fpw(int b, int e) {
if (e == 0)
return 1;
int r = fpw(b, e >> 1);
r = 1ll * r * r % p;
if (e & 1)
r = 1ll * r * b % p;
return r;
}
void check(int e) {
if (fpw(a, e) == 1)
ans = 0;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &a, &p);
ans = 1;
int phi = p - 1, r = phi;
for (int i = 2; i * i <= phi; i++)
if (phi % i == 0) {
check(phi / i);
while (r % i == 0)
r /= i;
}
if (r > 1)
check(phi / r);
printf(ans ? "Yes\n" : "No\n");
}
return 0;
}奇妙数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为一个数字 x 是奇妙数字当且仅当 x=pa,其中 p 为任意质数且 a 为正整数。例如, 8=23,所以 8 是奇妙数字,而 6 不是。
对于一个正整数 n ,小杨想要构建一个包含 m 个奇妙数字的集合{x1,x2,...,xm},使其满足以下条件:
集合中不包含相同的数字。
x1∗x2∗...∗xm是 n 的因子(即x1,x2,...,xm这 m 个数字的乘积是 n 的因子)。
小杨希望集合包含的奇妙数字尽可能多,请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数 n ,含义如题面所示。
输出格式
输出一个正整数,代表满足条件的集合最多包含的奇妙数字个数。
输入样例
输出样例
样例解释
关于本样例,符合题意的一个包含 3 个奇妙数字的集合是 2,4,8。首先,因为2=21,4=22,8=23, 所以 2,4,8 均为奇妙数字。同时,2∗4∗8=64 是 128 的因子。
由于无法找到符合题意且同时包含 4 个奇妙数字的集合,因此本样例的答案为 3 。

对于全部数据,保证有 2≤n≤1012。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
ll calc(ll x){
int ans = 0;
ll tmp=1;
while(x>=tmp){
ans++;
x-=tmp;
tmp++;
}
return ans;
}
int main(){
ll n;
cin>>n;
ll ans = 0;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
int cnt = 0;
while(n%i==0){
cnt++;
n/=i;
}
ans+=calc(cnt);
}
}
if(n!=1){
ans+=calc(1);
}
cout<<ans<<"\n";
}挑战怪物
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨正在和一个怪物战斗,怪物的血量为 h ,只有当怪物的血量恰好为 0 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式:
物理攻击。假设当前为小杨第 i 次使用物理攻击,则会对怪物造成 2i−1点伤害。
魔法攻击。小杨选择任意一个质数 x (x 不能超过怪物当前血量),对怪物造成 x 点伤害。由于小杨并不擅长魔法,他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物,如果能,小杨想知道自己最少需要多少次攻击。
输入格式
第一行包含一个正整数 t ,代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例,第一行包含一个正整数 h ,代表怪物血量。
输出格式
对于每组测试用例,如果小杨能够击败怪物,输出一个整数,代表小杨需要的最少攻击次数,如果不能击败怪物,输出−1。
输入样例
输出样例
对于第一组测试用例,一种可能的最优方案为,小杨先对怪物使用魔法攻击,选择质数 5 造成 5 点伤害,之后对怪物使用第 1 次物理攻击,造成21−1=1 点伤害,怪物血量恰好为 0 ,小杨成功击败怪物。

对于全部数据,保证有 1≤t≤10,1≤h≤105。
#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
bool is_prime[100010];
void Eratosthenes(int n) {
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i) is_prime[i] = true;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime.push_back(i);
if ((long long)i * i > n) continue;
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
}
int main() {
Eratosthenes(100000);
int t;
cin>>t;
while(t--){
int tmp=1;
int x;
cin>>x;
int ans=0;
while(1){
if(is_prime[x]){
ans++;
break;
}
x-=tmp;
ans++;
if(x<=0){
if(x<0)ans=-1;
break;
}
tmp*=2;
}
cout<<ans<<"\n";
}
}因数分解(2023.9C++五级)
时间限制:1.0 s
内存限制:128.0 MB
问题描述
每个正整数都可以分解成素数的乘积,例如:6=2×3、20=22×5
现在,给定一个正整数N,请按要求输出它的因数分解式。
输入描述
输入第一行,包含一个正整数N。约定2≤N≤1012
输出描述
输出一行,为N的因数分解式。要求按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格。
样例输入1
6
样例输出1
2 * 3
样例输入2
20
样例输出2
2^2 * 5
样例输入3
23
样例输出3
23
#include <iostream>
using namespace std;
int main() {
long long N = 0;
cin >> N;
bool first = true;
for (long long p = 2; p * p <= N; p++) {
if (N % p != 0)
continue;
int cnt = 0;
while (N % p == 0) {
cnt++;
N /= p;
}
if (first) {
first = false;
} else {
cout << " * ";
}
cout << p;
if (cnt > 1)
cout << "^" << cnt;
}
if (N > 1) {
if (first) {
first = false;
} else {
cout << " * ";
}
cout << N;
}
cout << endl;
return 0;
}