P16285 [蓝桥杯 2026 省 Python A 组] 可选数

Link: https://www.luogu.com.cn/problem/P16285

题目描述

给定 $N$ 个正整数 $A_1,A_2,\dots ,A_N$ 和一个目标整数 $K$。

如果一个正整数 $X$ 同时是 $A_1,A_2,\dots ,A_N$ 的公倍数，则我们称 $X$ 为一个可选数。

现在，你需要找到一个最小的正整数 $P$，使得对于任意一个可选数 $X$，$\text{lcm}(X,P)$（$X$ 和 $P$ 的最小公倍数）都能被 $K$ 整除。

输入格式

第一行包含两个整数 $N$ 和 $K$。

第二行包含 $N$ 个整数 $A_1,A_2,\dots ,A_N$。

输出格式

输出一个整数，表示满足条件的最小正整数 $P$。

输入输出样例 #1

输入 #1

3 12
6 4 9

输出 #1

1

输入输出样例 #2

输入 #2

2 10
4 6

输出 #2

5

说明/提示

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1\le N\le 20$，$1\le K,A_i\le 10^6$。

对于所有的评测用例，$1\le N\le 2\times 10^5$，$1\le K,A_i\le 10^{18}$。

---

Solution

1. 题意

给定了数组 { A N } \{A_N\} {AN​}，所有元素的公倍数称为可选数，记为 $X$。

对于给定的目标数字 $K$，求 $P$ 使得对任意一个可选数 $X$，$\text{lcm}(X,P)$ 均能被 $K$ 整除。

2. 分析

2.1 如何简化题目条件

可选数 $X$ 是 $A_1,A_2,\dots ,A_N$ 的公倍数，即 $X$ 一定是 $L=\text{lcm}(A_1,A_2,\dots ,A_N)$ 的倍数。

题目要求

$$\forall X,L\mid X⟹K\mid \text{lcm}(X,P)$$

很容易看出，只要这些 $A_i$ 的最小公倍数 $L$ 都能够满足条件，那么所有其他的公倍数必然都满足条件。

既然最苛刻的情况出现在最小的可选数 $X=L$ 时。因此原条件等价于：

$$K\mid \text{lcm}(L,P)$$

2.2 如何分解质因数

设 $v_q(n)$ 表示 $n$ 中质数 $q$ 的指数。$K\mid \text{lcm}(L,P)$ 等价于对任意质数 $q$ 均有关系：

$$\max (v_q(L),v_q(P))\ge v_q(K)$$

成立。

为了使 $P$ 最小，我们贪心地选择最小的 $v_q(P)\ge 0$。不难发现：

• 若 $v_q(L)\ge v_q(K)$，则条件已满足，取 $v_q(P)=0$（不再需要 $P$ 提供这种质因子）。
• 若 $v_q(L)<v_q(K)$，则必须满足 $v_q(P)\ge v_q(K)$，取最小值 $v_q(P)=v_q(K)$（$L$ 提供的质因子不够，$P$ 需要“独自”提供足量的质因子）。

总结起来，用通俗的话讲，就是为 $P$（初始为 $1$）补充所需的质因子，使得 $P$ 和 $L$ 作为“搭档”时，达到能够整除 $K$ 的最低门槛。

特别注意，这里同种质因子的指数不能 $L$ 和 $P$ 共同提供（这是最小公倍数的特性！），这是一个坑点！

2.3 如何判断 $v_q(L)\ge v_q(K)$

2.1 一节已经提到，只用考虑最小公倍数（记为 $L$）的情况即可。$L$ 作为所有这些 $A_i$ 的最小公倍数，其拥有的质因子的指数必然是所有 $A_i$ 的最大值。所以 $v_q(L)={\max }_i{v}_q(A_i)$。

从而有

$$v_q(L)\ge v_q(K)⟺\exists i,v_q(A_i)\ge v_q(K)⟺\exists i,q^{v_q(K)}\mid A_i$$
也就是说，我们只需要对 $K$ 的每个质因子幂 $q^e\parallel K$，检查是否存在某个 $A_i$ 能被 $q^e$ 整除。

• 若存在，说明 $L$ 已经包含了足够的 $q^e$，$P$ 不需要乘 $q^e$。
• 若不存在，说明 $L$ 缺少该质因子幂，$P$ 必须乘上 $q^e$。

概括起来还是 2.2 一节里的“补全整除门槛 + 不能‘合资’”的思想。

2.4 如何判断素数并从 $10^{18}$ 的数据范围里全身而退

就本例而言，对于大数，分解质因数需要使用 Miller-Rabin 素性检测算法 [1] 以及 Pollard’s rho 算法 [2]。就本题而言，只需要测定 $37$ 以内的质数，即可绝对确定素性。

分解出 $K=\prod q_j^{e_j}$ 后，对每个 $q_j^{e_j}$ 遍历数组 $A$ 检查整除性（是否“拥有”足够的质因子次数）即可。

3. 代码

import sys
import random

sys.setrecursionlimit(3000)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def miller_rabin(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n <= a: break
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def pollard_rho(n):
    if n % 2 == 0: return 2
    while True:
        x = random.randint(2, n - 1)
        y = x
        c = random.randint(1, n - 1)
        d = 1
        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            d = gcd(abs(x - y), n)
            if d == n: 
                break
        if d != 1 and d != n:
            return d

def factorize(n):
    factors = {}
    for p in [2, 3, 5]:
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p

    d = 7
    while d * d <= n and d <= 1000000:
        if n % d == 0:
            cnt = 0
            while n % d == 0:
                cnt += 1
                n //= d
            factors[d] = factors.get(d, 0) + cnt
        d += 2

    if n > 1:
        stack = [n]
        while stack:
            curr = stack.pop()
            if curr == 1: continue
            if miller_rabin(curr):
                factors[curr] = factors.get(curr, 0) + 1
            else:
                divisor = pollard_rho(curr)
                stack.append(divisor)
                stack.append(curr // divisor)
    return factors

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    N = int(next(it))
    K = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    if K == 1:
        print(1)
        return
    k_factors = factorize(K)
    P = 1
    for p, exp in k_factors.items():
        pe = p ** exp
        covered = False
        for a in A:
            if a % pe == 0:
                covered = True
                break
        if not covered:
            P *= pe
            
    print(P)

if __name__ == "__main__":
    solve()