题目来源: 2020 CCPC Wannafly 冬令营 Day1: H. 最大公约数

题面

一共 \(T\) 组数据.

现有一个未知的整数 \(k\), 满足 \(1\le k\le n\).

现在你被宣称 \(k\) 的值等于 \(x\), 但是你不知道真假. 你现在可以提交一个任意大的正整数 \(y\), 之后获得返回值 \(\gcd(k,y)\).

你需要输出一个合适的 \(y\), 使得你可以通过返回值来查验 \(x\) 和 \(k\) 是否相等. 如果有很多满足条件的值, 输出最小的那个. 如果没有合适的 \(y\), 输出 \(-1\).

简要描述

给定 \(n, x\), 试给出一个最小 \(y\), 使得 \(\forall 1\le a\le n\), 若 \(a\ne x\), 则 \(\gcd(a,y)\ne \gcd(x,y)\).

数据范围

\[ 1\le T\le 50 \]

\[ 1\le k\le n\le500 \]

题解

注意到 \(\gcd(x,y)=\gcd(\gcd(x,y),y)\), 于是应满足 \(\gcd(x,y)=x\), 即 \(x\mid y\). 设 \(y=xy'\).

若 \(x\nmid a\), 则显然 \(\gcd(a,y)\ne x\). \(\forall a'\in(1,n/x]\), 都有 \(\gcd(a'x,y)=x\gcd(a',y')\), 于是此时 \(\gcd(a',y')\ne 1\). 考虑到: 对于任意 \((1,n/x]\) 中的素数 \(p\), 亦都应该有 \(\gcd(p,y')\ne 1\), 此时有 \(\gcd(p,y')=p\), \(p\mid y'\). 于是这些素数的乘积 \(P\) 满足 \(P\mid y'\). \(P\le y'\).

若 \(P=y'\), 则 \(\forall a'\in (1,n/x]\), \(a'\) 的任意素因子 \(p\) 一定满足 \(1<p\le a'\le n/x\), \(p\mid y\), 于是 \(\gcd(a',y')\ne 1\), \(\gcd(a'x,y)\ne x\).

于是取 \(P=y'\) 是可行的, 而且是最小的解.

预处理 \([1,500]\) 中的所有素数, 解就是 \[ y=x\prod_{p\le n/x}p \] 由于 \(y\) 的可能的最大值超过了 \(2^{128}\), 于是应该使用高精度乘法, 或者使用 Python.

忽略高精度乘法的复杂度常数. 若每次询问暴力计算素数乘积, 则复杂度为 \(O(Tn)\). 若采用前缀积, 则复杂度为 \(O(T+n)\).

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
prime = [2,3,5,7,11,13,17,19,...,599] 
# 600以内的素数请自己打表补全, 这里省略.
ts = 0
hds = [1]
for i in range (1, 600):
    if (prime[ts] == i):
        hds.append(int(prime[ts] * hds[i - 1]))
        ts += 1
    else:
        hds.append(hds[i - 1])
t = int(input())
for rt in range (0, t):
    n, k = map(int, input().split(' '))
    print(k * hds[n // k])