2020 CCPC-Wannafly Winter Camp Day 1 H | Nanako

2020 CCPC-Wannafly Winter Camp Day 1 H

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

欢迎关注我的其它发布渠道