【2022天梯赛暑期集训】第四次试题（分解质因数、大整数运算、扩展欧几里得算法、组合数）

https://pintia.cn/problem-sets/1547030907058900992/problems/type/7

https://bytodance.feishu.cn/docx/doxcnlU4LYJDgWIdAcmpHloAMoe

7-1 分解质因数

分数 10

作者 林生佑

单位 浙江传媒学院

求出区间[a,b]中所有整数的质因数分解，2<=a<=b<=10000。

输入格式:

输入两个整数a，b。

输出格式:

每行输出一个数的分解，形如k=a1_a2_a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)

输入样例:

3 10

输出样例:

3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

AC 代码

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
int cnt, primes[N];
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            for (int j = i; j <= n; j += i) st[j] = true;
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    get_primes(b);
    for (int i = a; i <= b; i++) {
        int t = i;
        vector<int> res;

        for (int j = 0; j < cnt && primes[j] < t; j++) {
            if (t % primes[j] == 0) {
                while (t % primes[j] == 0) {
                    res.push_back(primes[j]);
                    t /= primes[j];
                }
            }
        }
        if (t > 1) res.push_back(t);

        cout << i << '=';
        for (int j = 0; j < res.size(); j++) {
            if (j > 0) cout << '*';
            cout << res[j];
        }
        cout << endl;
    }

    return 0;
}

7-2 “接肢”葛瑞克

分数 20

作者 xxxtentx

欢迎来到交界之地，褪色者。
恶名昭彰的BOSS“接肢”葛瑞克通过接肢来提升自己的力量，但是最初的葛瑞克十分弱小，接肢数量仅为可怜的1。接下来褪色者会和葛瑞克进行战斗。
假设褪色者面对葛瑞克战败后，再一次挑战葛瑞克时，葛瑞克会在自己原来的身体上通过接肢加强自己的力量，而接肢的数量是以指数递增的。比如褪色者第二次挑战时（假设褪色者不可能第一次就打败葛瑞克），接肢的数量就是第一次的数量 * 2，第三次挑战就是第二次的数量 * 3，以此类推。
褪色者通过攻击来解肢击败葛瑞克，而褪色者的攻击伤害只有质数才会对BOSS造成伤害，合数的攻击对于BOSS无效。且每次攻击伤害都只能从2开始，除非本次攻击无法完全整数解肢（比如接肢数量为21时，伤害为2无法解肢，只有伤害增加到3时才可以攻击BOSS解肢，攻击后接肢数量为7），那么就会伤害增加一点继续攻击BOSS。
当葛瑞克的接肢数量回到最初的起点的时候，即为战胜BOSS。

输入格式:

题目给出褪色者最终战胜葛瑞克所挑战的次数n。

输出格式:

题目要求你输出战胜葛瑞克时，褪色者的攻击的伤害a和伤害a的攻击次数b，a和b之间用空格隔开。并且每一组伤害独占一行输出，且每一行依次递增的输出伤害。

数据范围:

2 ≤ n ≤ 106

输入样例:

5

输出样例:

2 3
3 1
5 1

AC 代码

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;

const int N = 1e6 + 10;
int cnt, primes[N];
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            for (int j = i; j <= n; j += i) st[j] = true;
        }
    }
}

int main() {
    get_primes(1e6);
    int n;
    // 题目给出褪色者最终战胜葛瑞克所挑战的次数n。
    cin >> n;
    // 第几次打败葛瑞克
    int cnt = 1;
    // 当前接肢数量
    int cur = 2;
    // 接肢的数量是以指数递增
    int exp = 2;
    // 当前攻击的力度，必须是质数，所以就用primes[]数组的下标表示
    int idx = 0;
    map<int, int> mp;
    do {
        // 只有质数才会对BOSS造成伤害 整数解肢
        if (cur % primes[idx] == 0) {
            cur /= primes[idx];
            mp[primes[idx]]++;
            idx = 0;
        } else
            idx++;
        // 如果回到了1，证明被战胜了
        if (cur == 1) {
            cnt++;
            cur = 1;
            // 接肢的数量是以指数递增的
            cur *= (++exp);
        }
    } while (cnt != n);
    // 输出结果
    for (auto it : mp) cout << it.first << " " << it.second << endl;
    return 0;
}

7-3 大整数A+B

分数 5

全屏浏览题目

切换布局

作者 HDOJ

单位 绍兴文理学院

输入两个整数A、B，求 A + B。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入2个正整数A、B。整数可能很大，但每个整数的位数不会超过1000。

输出格式:

对于每组测试输出两行数据；第一行输出”Case #:”，#表示测试组号，第二行输出形式为“A + B = Sum”，Sum表示A+B的结果。每两组测试数据之间空一行。

输入样例:

2
1 2
88888888888888888888888 11111111111111111111111

AC 代码

输出样例:

Case 1:
1 + 2 = 3

Case 2:
88888888888888888888888 + 11111111111111111111111 = 99999999999999999999999

出处:

HDOJ 1002

T = int(input())
for i in range(1, T + 1):
    a, b = map(int, input().split())
    print('Case %d:' % i)
    print(a, '+', b, '=', a + b)
    if i != T:
        print()

7-4 大整数A-B

分数 5

全屏浏览题目

切换布局

作者 xxxtentx

给定两个正整数（不含前导0），计算它们的差，计算结果可能为负数。

输入格式:

共两行，每行包含一个整数。

输出格式:

共一行，包含所求的差。

数据范围:

1 ≤ 整数长度 ≤ 105

输入样例:

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

32
11

输出样例:

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

21

AC 代码

a = int(input())
b = int(input())
print(a - b)

7-5 高精度A * 低精度b

分数 5

作者 xxxtentx

给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。

输入格式:

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式:

共一行，包含 A×B 的值。

数据范围:

1 ≤ A的长度 ≤ 100000,
0 ≤ B ≤ 10000

输入样例:

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

2
3

输出样例:

6

AC 代码

a = int(input())
b = int(input())
print(a * b)

7-6 整除光棍

分数 20

作者 翁恺

单位 浙江大学

这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

输入格式：

输入在一行中给出一个不以5结尾的正奇数x（<1000）。

输出格式：

在一行中输出相应的最小的s和n，其间以1个空格分隔。

输入样例：

31

输出样例：

3584229390681 15

AC 代码

模拟除法，先找到一个比所求大的111…，再输出除以n的商

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, chushu = 1, weishu = 1;
    cin >> n;
    // 先找到一个比所求大的111...
    while (chushu < n) {
        chushu = chushu * 10 + 1;
        weishu++;
    }
    while (1) {
        // 再输出除以n的商
        cout << chushu / n;
        // 如果整除就返回
        if (chushu % n == 0) break;
        // 加一个 1 继续除
        chushu = (chushu % n) * 10 + 1;
        // 位数 + 1
        weishu++;
    }
    cout << ' ' << weishu;
    return 0;
}

7-7 h0054. 欧几里得的问题

分数 10

全屏浏览题目

切换布局

作者 黄正鹏

单位 贵州工程应用技术学院

由欧几里得的辗转相除法可知，对于任何正整数 A
和 B ，都存在这样的整数 X 和 Y ， AX+BY=D ，其中 D 是
A 和 B 的最大公约数。本题要求，对于给定的 A 和 B ，
找到对应的 X ， Y 和 D 。

输入格式:

输入给出一些行，每行由空格隔开的整数 A 和 B 组成， 0<A,
B<1000000001 。

输出格式:

对于每个输入行，输出一行，由三个用空格隔开的整数 X 、 Y 和 D组成。如果有若干个满足条件的 X 和 Y ，那么就输出 |X |+|Y| 最小的那对。如果还是有若干个 X 和 Y 满足最小准则，则输出 X≤Y 的那一对。

输入样例:

4 6
17 17

输出样例:

-1 1 2
0 1 17

AC 代码

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1, gcd;
    gcd = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return gcd;
}
int main() {
    int a, b, x, y;
    while (cin >> a >> b) {
        exgcd(a, b, x, y);
        cout << x << " " << y << " " << a * x + b * y << endl;
    }
    return 0;
}

7-8 组合数问题

分数 25

全屏浏览题目

切换布局

作者 CCF_NOIP

组合数 Cnm​ 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 Cnm​ 的一般公式：

Cnm​=m!(n−m)!n!​

其中 n!=1×2×⋯×n；特别地，定义 0!=1。

小葱想知道如果给定 n,m 和 k，对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足 Cij​ 是 k 的倍数。

输入格式:

第一行有两个整数 t,k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见问题描述。

接下来 t 行每行两个整数 n,m，其中 n,m 的意义见问题描述。

输出格式:

共 t 行，每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满足 Cij​ 是 k 的倍数。

数据范围:

0≤n,m≤2×103,
2≤k≤21,
1≤t≤104

输入样例:

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

1 2
3 3

输出样例:

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

1

提示

【样例说明】

在所有可能的情况中，只有 C21​=2 一种情况是 2 的倍数。

AC 代码

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 2010;

int c[N][N];
// 前缀和
int s[N][N];

int main() {
    int T, k;
    scanf("%d%d", &T, &k);

    // 预处理前缀和
    
    for (int i = 0; i < N; i++)
        // 求余数
        for (int j = 0; j <= i; j++) {
            if (j == 0)
                c[i][j] = 1 % k;
            else
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
            // 如果是余数0，就代表就有一次
            if (c[i][j] == 0) s[i][j] = 1;
        }
    // 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            if (i != 0) s[i][j] += s[i - 1][j];
            if (j != 0) s[i][j] += s[i][j - 1];
            if (i != 0 && j != 0) s[i][j] -= s[i - 1][j - 1];
        }

    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);

        printf("%d\n", s[n][m]);
    }

    return 0;
}