【2022天梯赛暑期集训】第二次试题（进制转换，公约数公倍数，素数筛，欧拉函数）

发表于

https://pintia.cn/problem-sets/1546381984669618176

7-1 求素数

分数 5

作者 唐艳琴

单位 中国人民解放军陆军工程大学

本题目要求读入1个正整数A，判断A是否为素数。

输入格式:

输入1个正整数A。

输出格式:

输出A是或否为素数。

输入样例:

1
2

输出样例:

1
2 yes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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的十进制整数。

输出格式:

在一行内输出对应的二进制数、八进制数和十六进制数，以空格隔开。

输入样例:

在这里给出一组输入。例如：

1
8

输出样例:

在这里给出相应的输出。例如：

1
1000 10 8
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
#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区间有多少个素数。

输入样例:

1
10

输出样例:

1
4
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
#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的最大公约数和最小公倍数。

输入样例:

1
16 24

输出样例:

1
8 48
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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=p^a1p^a2…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 中每个数的欧拉函数之和。

输入样例:

1
2
3
4
3
3
6
8

输出样例:

1
2
3
2
2
4
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
#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

输入样例:

在这里给出一组输入。例如：

1
6

输出样例:

在这里给出相应的输出。例如：

1
12
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
#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’表示1035

输入格式:

第1行：1个n，表示指令数量
　　第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出格式
　　依次给出每一次’EQUAL’得到的结果

输出格式:

依次给出每一次’EQUAL’得到的结果

输入样例:

1
2
3
4
5
6
7
8
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL

输出样例:

1
2040
1
蓝桥杯国赛题，下次一定写...