Problem H. 最大公约数
Statement
给出两个整数 $k,n$ （$1 \leq k \leq n$），求最小的 $y$，使得对于任意 $x \in [1,n]$ 且 $x \neq k$，都满足 $\gcd(x, y) \neq \gcd(k,y)$。如果不存在这样的 $y$，输出$-1$。有 $T$ 组测试数据。
$1 \leq T \leq 50$
$1 \leq k \leq n \leq 500$
Solution
不存在这样的 $y$ 当然是骗你的，因为一定存在……
我在狂演 F 题的时候这题就有一些队伍过了，于是 Luowaterbi 和 owojiecao 就在看，但是没什么结论……我演完 F 之后看了一会样例，猜想答案就是 $k \cdot \prod_{i = 1, i \in p}^{\lfloor \frac{n}{k} \rfloor} i$，虽然不会证明但是我们三个都没想到反例，于是我就交了两发 WA，发现需要高精度，用 Java 重写，过了。
抄了一个必要性证明大概是这样的：
- 必须保证 $k|y$。否则就有 $\gcd(k,y) \neq k$，又因为显然 $\gcd(k,y) = \gcd(\gcd(k,y),y)$，就不符合题意了啊。
- 对于 $[1,\lfloor \frac nk \rfloor]$ 中的每一个质数 $p$，必须保证 $p|\frac yk$。否则就有 $\gcd(pk,y) = k \cdot \gcd(p,y/k) = k =\gcd(k,y)$，就不符合题意了啊。
充分性问就是不会证啊，proof by AC。
Code
这是不带高精度 WA 掉的版本。
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
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 5;
const int M = 1e3;
ll flag[N], pri[N];
void sieve () {
for (int i = 2;i < M;i++) {
if (!flag[i])
pri[++pri[0]] = i;
for (int j = 1;j <= pri[0] && pri[j] * i < M;j++) {
flag[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
}
int main () {
sieve();
int T;
scanf("%d", &T);
while (T--) {
ll n, k;
scanf("%lld%lld", &n, &k);
ll p = 1, ans = k;
while (k * pri[p] <= n) {
ans *= pri[p];
p++;
}
printf("%lld\n", ans);
}
return 0;
}
|
这是带高精度的 Java 版本。我实在是不会 Java，勉强照着上面的 C++ 打的，如果写得很傻逼请不要 D 我呜呜呜
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
| import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main (String args[]) {
final int N = 1000;
int flag[] = new int[N];
int pri[] = new int[N];
for (int i = 2;i < N;i++) {
if (flag[i] == 0) pri[++pri[0]] = i;
for (int j = 1;j <= pri[0] && i * pri[j] < N;j++) {
flag[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
for (int it = 1;it <= T;it++) {
int n = scan.nextInt();
int k = scan.nextInt();
int p = 1;
BigInteger ans = new BigInteger(k + "");
while (k * pri[p] <= n) {
ans = ans.multiply(BigInteger.valueOf(pri[p]));
p++;
}
System.out.println(ans);
}
}
}
|