https://pintia.cn/problem-sets/1546381984669618176
7-1 求素数
分数 5
作者 唐艳琴
单位 中国人民解放军陆军工程大学
本题目要求读入1个正整数A，判断A是否为素数。
输入格式:
输入1个正整数A。
输出格式:
输出A是或否为素数。
输入样例:
2
输出样例:
2 yes
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
bool isPrime(LL t) {
if (t < 2) return false;
for (LL i = 2; i <= t / i; i++)
if (t % i == 0) return false;
return true;
}
int main() {
LL t;
cin >> t;
cout << t << ' ' << (string)(isPrime(t) ? "yes" : "no") << endl;
return 0;
}
7-2 进制转换
分数 5
作者 wangxj
单位 临沂大学
输入一个十进制的整数。将它转换为二进制数、八进制数和十六进制数。
输入格式:
输入一个不超过100的十进制整数。
输出格式:
在一行内输出对应的二进制数、八进制数和十六进制数，以空格隔开。
输入样例:
在这里给出一组输入。例如：
8
输出样例:
在这里给出相应的输出。例如：
1000 10 8
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
void to_2(int n) {
int a[1000];
int num = 0;
do {
a[num++] = n % 2;
n /= 2;
} while (n != 0);
for (int i = num - 1; i >= 0; i--) cout << a[i];
cout << ' ';
return;
}
void to_8(int n) {
int a[1000];
int num = 0;
do {
a[num++] = n % 8;
n /= 8;
} while (n != 0);
for (int i = num - 1; i >= 0; i--) cout << a[i];
cout << ' ';
return;
}
char h[17] = {'0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
void to_16(int n) {
int a[1000];
int num = 0;
do {
a[num++] = n % 16;
n /= 16;
} while (n != 0);
for (int i = num - 1; i >= 0; i--) cout << h[a[i]];
return;
}
int main() {
int t;
cin >> t;
to_2(t);
to_8(t);
to_16(t);
return 0;
}
7-3 欧拉筛
分数 10
作者 c++课程组
单位 湖州师范学院
求1~n区间有多少个素数。（n<4×107）
输入格式:
一个数n
输出格式:
一个数，表示1~n区间有多少个素数。
输入样例:
10
输出样例:
4
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4e7 + 10;
//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) primes[cnt++] = i;
//假设primes[0]为n最小的质因子,i为最大的因数，
//易知若primes[i]中i>0,则会进入循环后产生多余的标记。
for(int j = 0; primes[j] <= n / i; j ++)
{
//标记;primes[j]一定是primes[j]*i的最小质因子
st[primes[j]*i] = true;
//表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
//这样能保证每个数遍历一遍,而没有重复
if(i % primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
7-4 最大公约数和最小公倍数
分数 10
作者 李体新
单位 保定学院
本题目要求读入2个正整数A和B，输出它们的最大公约数和最小公倍数。
输入格式:
输入在一行中给出2个绝对值不超过1000的整数A和B。
输出格式:
在一行中输出A和B的最大公约数和最小公倍数。
输入样例:
16 24
输出样例:
8 48
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main() {
int a,b;
cin >> a >> b;
cout << gcd(a,b) << ' ' << a * b / gcd(a,b)<< endl;
return 0;
}
7-5 欧拉函数
分数 10
作者 杜祥军
单位 青岛大学
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)。
若在算数基本定理中，N=pa1pa2…pa^m，则：
ϕ(N) = N×(p1−1)/p1×(p2−1)/p2×…×(pm−1)/pm;
输入格式:
第一行输入一个n，接下来行每行包含一个正整数ai，输出ai的欧拉函数。
数据范围：1<=n<=100，1<=ai<=2*10^9
输出格式:
共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
输入样例:
3
3
6
8
输出样例:
2
2
4
#pragma GCC optimize(2)
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int phi(int x) {
int res = x;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int main() {
int n;
cin >> n;
int x;
while (n--) {
cin >> x;
cout << phi(x) << endl;
}
return 0;
}
7-6 求欧拉函数之和
分数 15
全屏浏览题目
切换布局
作者 aa
单位 江西财经大学
给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
输入格式:
共一行，包含一个整数 n。
输出格式:
共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
数据范围:
1≤n≤10^6
输入样例:
在这里给出一组输入。例如：
6
输出样例:
在这里给出相应的输出。例如：
12
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int primes[N], cnt; // primes数组存所有的质因子，cnt是下标
int phi[N]; //欧拉函数
bool st[N]; //表示每个数是否被筛掉了
LL get_eulers(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) { //线性筛
if (!st[i]) { //当前没有被筛过就是质数
primes[cnt++] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) {
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
LL res = 0;
for (int i = 1; i <= n; i++) res += phi[i];
return res;
}
int main() {
int n;
cin >> n;
cout << get_eulers(n) << endl;
return 0;
}
7-7 小计算器
分数 20
作者 aa
单位 江西财经大学
模拟程序型计算器，依次输入指令，可能包含的指令有
1. 数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
2. 运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
3. 进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
4. 输出指令：‘EQUAL’，以当前进制输出结果
5. 重置指令：‘CLEAR’，清除当前数字
指令按照以下规则给出：
数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
进制转换指令可能出现在任何地方
运算过程中中间变量均为非负整数，且小于2^63。
以大写的'A'~'Z'表示10~35
输入格式:
第1行：1个n，表示指令数量
第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出格式
依次给出每一次’EQUAL’得到的结果
输出格式:
依次给出每一次’EQUAL’得到的结果
输入样例:
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
输出样例:
2040
蓝桥杯国赛题，下次一定写...