2025寒假算法练习——Week 4
文章目录
习题均来自 NEFU OJ
Problem 1077 | 最大公约数和最小公倍数
- Description
请计算2个数的最大公约数和最小公倍数；（最大公约数可以使用辗转相除法，最小公倍数=2个数的乘积/它们的最大公约数；）
- Input
输入数据有多组，每组2个正整数a,b(2<a,b<1000)
- Output
在一行内输出a和b的最大公约数和最小公倍数；
- Sample Input
115 10
- Sample Output
15 30
1import java.util.Scanner;
2
3public class Main {
4 public static void main(String[] args) {
5 Scanner scanner = new Scanner(System.in);
6 while (scanner.hasNextInt()) {
7 int a = scanner.nextInt();
8 int b = scanner.nextInt();
9 int d = gcd(a, b);
10 int m = a * b / d;
11 System.out.println(String.format("%d %d", d, m));
12 }
13 scanner.close();
14 }
15
16 public static int gcd(int a, int b) {
17 return b == 0 ? a : gcd(b, a % b);
18 }
19}
Problem 992 | 又见 GCD
- Description
有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。
- Input
每行输入两个正整数a,b。
- Output
输出对应的c，每组测试数据占一行
- Sample Input
16 2
212 4
- Sample Output
14
28
已知 $GCD(a,c)=b$ 且 $b\neq c$，求满足条件的最小 c。根据性质知道 $c=b\cdot p$，其中 $p\nmid a\div b$ 且 $p\in\mathbb{P}$。只需遍历 p 即可。
1import java.util.Scanner;
2
3public class Main {
4 public static void main(String[] args) {
5 int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
6 try (Scanner scanner = new Scanner(System.in)) {
7 int a, b, i;
8 while (scanner.hasNextInt()) {
9 a = scanner.nextInt();
10 b = scanner.nextInt();
11 a /= b;
12
13 for (i = 0; i < 10; i++) {
14 if (a % prime[i] != 0) {
15 System.out.println(b * prime[i]);
16 break;
17 }
18 }
19 }
20 }
21 }
22}
Problem 764 | 多个数的最大公约数
- Description
给定n(n<=10)个正整数，你的任务就是求它们的最大公约数，所有数据的范围均在long long内。
- Input
输入数据有多组，每组2行，第一行为n，表示要输入数字的个数，接下来第二行有n个正整数。
- Output
输出一个数，即这n个数的最大公约数。
- Sample Input
15
22 4 6 8 10
32
413 26
- Sample Output
12
213
先求前两数的 gcd，再用每次求出的 gcd 依次和下一个数求 gcd。
1import java.util.Scanner;
2
3public class Main {
4 public static void main(String[] args) {
5 int n, a, b;
6 try (Scanner sc = new Scanner(System.in)) {
7 while (sc.hasNextInt()) {
8 n = sc.nextInt();
9 a = sc.nextInt();
10
11 for (int i = 1; i < n; i++) {
12 b = sc.nextInt();
13 a = gcd(a, b);
14 }
15
16 System.out.println(a);
17 }
18 }
19 }
20
21 public static int gcd(int a, int b) {
22 return b == 0 ? a : gcd(b, a % b);
23 }
24}
Problem 765 | 多个数的最小公倍数
- Description
给定n(n<=10)个正整数，你的任务就是求它们的最小公倍数，所有数据的范围均在long long内。
- Input
输入数据有多组，每组2行，第一行为n，表示要输入数字的个数，接下来第二行有n个正整数。
- Output
输出一个数，即这n个数的最小公倍数。
- Sample Input
15
22 4 6 8 10
32
413 26
- Sample Output
1120
226
依次将当前两数的最大公倍数和下一个数计算最大公倍数即可。
1import java.util.Scanner;
2
3public class Main {
4 public static void main(String[] args) {
5 int n, a, b, d, m;
6 try (Scanner sc = new Scanner(System.in)) {
7 while (sc.hasNextInt()) {
8 n = sc.nextInt();
9 a = sc.nextInt();
10 d = a;
11 m = a;
12
13 for (int i = 1; i < n; i++) {
14 b = sc.nextInt();
15 d = gcd(m, b);
16 m *= b / d;
17 }
18
19 System.out.println(m);
20 }
21 }
22 }
23
24 public static int gcd(int a, int b) {
25 return b == 0 ? a : gcd(b, a % b);
26 }
27}
注意
$LCM(a_1,a_2,\cdots,a_n)$ 与 $\frac{\prod_{i=1}^na_i}{GCD(a_1,a_2\cdots,a_n)^n}$ 不一定相等。
Problem 1411 | LCM&GCD
- Description
jwGG最近沉迷于数论，他最近在研究最小公倍数和最大公约数，他的队友yzMM正好对数论也有些研究，于是yzMM给jwGG出了一个简单的数论题：在[x,y]区间中，求两个整数最大公约数是x且最小公倍数是y的个数。
yzMM善意地提醒，x和y可能到1e12那么大，jwGG这下可犯了难，这到底该怎么做呢？聪明的你能帮帮他吗？
- Input
第一行输入一个T(T<=100)，表示有T组数据，接下来每组输入两个数x,y(1<=x<=y<=1e12)(含义如题)
- Output
输出一行表示答案。
- Sample Input
11
22 12
- Sample Output
14
- Hint
(2,12) (4,6) (6,4) (12,2)
- Source
ITAK 2020.1.28 数据已加强
根据性质，$GCD(a,b)\cdot LCM(a,b)=a\cdot b$。因此将 x 与 y 相乘并分解质因数，随后在其因数中遍历（深搜）找到符合条件的 a 与 b。注意两种特判，一种是当 x 与 y 相等时解唯一，一种是当 $x\nmid y$ 时无解。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <map>
5#include <cmath>
6
7#define ll long long
8
9using namespace std;
10
11int ans;
12ll x, y, mul;
13
14ll gcd(ll a, ll b) {
15 return b == 0 ? a : gcd(b, a % b);
16}
17
18void dfs(map<ll, ll>& factors, int k, int l, ll cur) {
19 if (k == l) {
20 ll t = mul / cur;
21 if (t >= x && t <= y && cur >= x && cur <= y && t % cur != 0 && cur % t != 0 && gcd(t, cur) == x) {
22 ans++;
23 }
24 return;
25 }
26
27 auto it = factors.begin();
28 advance(it, k);
29 for (int i = 0; i <= it->second; i++) {
30 ll p = pow(it->first, i);
31 cur *= p;
32 dfs(factors, k + 1, l, cur);
33 cur /= p;
34 }
35
36 return;
37}
38
39map<ll, ll> pfd(ll a) {
40 map<ll, ll> factors;
41 ll count = 0;
42 while (a % 2ll == 0) {
43 a /= 2ll;
44 count++;
45 }
46 if (count > 0) {
47 factors[2] = count;
48 }
49
50 ll k = 3;
51 while (k * k <= a) {
52 count = 0;
53 while (a % k == 0) {
54 a /= k;
55 count++;
56 }
57 if (count > 0) {
58 factors[k] = count;
59 }
60 k += 2;
61 }
62
63 if (a > 2) {
64 factors[a] = 1;
65 }
66 return factors;
67}
68
69int main() {
70 int n;
71 scanf("%d", &n);
72 while (n--) {
73 scanf("%lld%lld", &x, &y);
74
75 if (y % x != 0) {
76 printf("0\n");
77 continue;
78 }
79
80 if (x == y) {
81 printf("1\n");
82 continue;
83 }
84
85 mul = x * y;
86 map<ll, ll> factors = pfd(mul);
87 ans = 0;
88 dfs(factors, 0, factors.size(), 1);
89 printf("%d\n", ans + 2);
90 }
91 return 0;
92}
Problem 1669 | 高木同学的因子
- Description
今天西片同学又被高木同学捉弄了，高木同学跟西片同学玩了这么一个游戏。两人心中分别想一个数字，这两个数字分别为x和y（1<=x,y<=1e18），然后让西片同学说出一共有多少个整数既是x的因子，又是y的因子。由于西片和高木很有默契，所以保证他们两个想的数x和y的最大公因数不会超过1e9。这个问题又难住了西片同学了，你能帮帮西片同学告诉他答案吗？
- Input
单组输入 数据占一行，包含两个整数x和y（1<=x,y<=1e18），保证gcd（x,y）<=1e9。
- Output
输出既是x因子又是y因子的整数的个数。输出占一行
- Sample Input
112 36
- Sample Output
16
- Hint
12和36有共同因子1 2 3 4 6 12共计6个数字，所以答案为6
- Source
GYL
这是一道数学题（数论题），直接枚举会超时。因为两数的公因数均为其最大公因数的因数，所以只计算两数最大公因数的因数个数即可。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5#define ll long long
6
7inline ll gcd(ll a, ll b) {
8 return b == 0 ? a : gcd(b, a % b);
9}
10
11int main() {
12 ll a, b;
13 scanf("%lld%lld", &a, &b);
14 ll d = gcd(a, b), i, count = 0;
15 for (i = 1; i * i < d; i++) {
16 if (d % i == 0) {
17 count += 2;
18 }
19 }
20 if (i * i == d) {
21 count++;
22 }
23 printf("%lld\n", count);
24 return 0;
25}
Problem 601 | 快速幂取模
- Description
给定A,B,C，计算A^B%C，这里A^B代表A的B次方。
- Input
输入数据有多组，每组数据一行，有3个正整数分别为A,B和C，1<=A,B,C<=1000000000
- Output
输出A^B%C的值
- Sample Input
12 3 5
28 2 10
- Sample Output
13
24
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5#define ll long long
6
7int main() {
8 ll b, e, m, result;
9 while (scanf("%lld %lld %lld", &b, &e, &m) == 3) {
10 result = 1;
11 b %= m;
12 while (e > 0) {
13 if (e & 1) {
14 result = (result * b) % m;
15 }
16 b = (b * b) % m;
17 e >>= 1;
18 }
19 printf("%lld\n", result);
20 }
21 return 0;
22}
Problem 1666 | 库特的数学题
- Description
库特很喜欢做各种高深莫测的数学题，一天，她在书上看到了这么一道题。a[1]=6,a[2]=18;a[n]=2*a[n-1]+3*a[n-2](n>=3),对于给出的某个数字n，求a[n]。库特一想这道题太简单了，可是看到n的范围是（n<=1e18），对于这么大范围的数，库特不知道该怎么做了，聪明的你，快来帮帮库特解决这个问题吧。（由于答案可能很大，请将答案对1e9+7（即1000000007）取模）。
- Input
一个整数n（1<=n<=1e18）
- Output
a[n]对1e9+7取模后的答案
- Sample Input
15
- Sample Output
1486
做这道题还要我复习高考数学……最后算（瞪）出来通项公式为 $a_n=2\cdot3^n$，后面要用快速幂取模。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5#define ll long long
6
7const ll MOD = 1e9 + 7;
8
9int main() {
10 ll n;
11 scanf("%lld", &n);
12 ll result = 1, b = 3;
13 while (n > 0) {
14 if (n & 1) {
15 result = (result * b) % MOD;
16 }
17 b = (b * b) % MOD;
18 n >>= 1;
19 }
20 printf("%lld\n", result * 2 % MOD);
21 return 0;
22}
Problem 1834 | 异或方程解的个数
- Description
ljw这几天给大一同学讲课的时候，觉得自己太菜了，于是他做了一道无聊的数学题，但是他觉得这题太难了，所以他把问题交给了聪明的你，你能帮他解决这个问题吗？
问题如下：
给你一个方程：n−(n^x)−x=0 (其中 ^ 表示两个数异或，并不是表示幂次符号哦)
现在给你n的值，问有多少种x的取值使得方程成立（数据保证n在2的30次方范围内）
- Input
多组输入数据（不超过2000000组） 每组输入数据包含一个整数n，含义如题。
- Output
对于每组输入数据，你需要输出一个整数，表示解的个数。
- Sample Input
10
22
- Sample Output
11
22
- Hint
异或指的是，两个数的每一个二进制位，如果相同，异或结果为0，如果不相同，异或结果为1。
样例解释：
当n=0时，可以证明x只有等于0时才满足方程，此时x只有1种满足条件的取值，所以输入的n=0时，你需要输出1。
- Source
原题：AotoriChiaki 改编：nefu_ljw
首先对方程做变换得到 $n-x=n\oplus x$，观察得到，此时对于 n 与 x，异或与相减得到的结果相同。根据异或的性质不难想到，当 n 与 x 的某一位同时为 1 时，$n-x=n\oplus x$ 成立（通过与空格异或实现大小写转换也是同样的原理）。因此只要统计出 n 的二进制表示中有多少个 1，然后找出所有的组合即可。假设 n 的二进制表示中有 m 个 1，则 x 共有 $2^m$ 种可能。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5using namespace std;
6
7int main() {
8 int n, result;
9 while (scanf("%d", &n) == 1) {
10 result = 1;
11 while (n > 0) {
12 if (n & 1) {
13 result <<= 1;
14 }
15 n >>= 1;
16 }
17 printf("%d\n", result);
18 }
19}