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;
}