把质数拆成两组生成所有乘积，二分答案并双指针统计不超过它的乘积对数。
OJ: luogu
题目 ID: CF912E
难度:省选/NOI-
标签:Meet-in-the-Middle二分答案数论python
日期: 2026-07-16 20:10
题意
给定至多 16 个质数，求所有质因子都来自该集合的第 k 小正整数，答案不超过
思路
把质数交错分到两组，分别 DFS 枚举不超过 left * right。
二分候选答案 limit。两边乘积列表升序后，用一个只向左移动的右指针统计满足 left[i] * right[j] <= limit 的配对数。计数至少 k 时收缩上界。
乘法比较写成 left > limit // right，避免其他语言中的 64 位溢出。
Python 知识
primes[::2]与primes[1::2]交错拆分，比按连续位置切分更平衡小质数。- 递归中的
while自然枚举某质数指数为 0、1、2……。 - Python 大整数不会溢出，但除法比较仍更便于迁移到 C++。
代码
python
import sys
LIMIT = 10**18
input = sys.stdin.buffer.readline
n = int(input())
primes = list(map(int, input().split()))
rank = int(input())
def products(selected):
result = []
def dfs(index, value):
if index == len(selected):
result.append(value)
return
prime = selected[index]
while value <= LIMIT:
dfs(index + 1, value)
if value > LIMIT // prime:
break
value *= prime
dfs(0, 1)
return sorted(result)
left = products(primes[::2])
right = products(primes[1::2])
def count_not_greater(limit):
count = 0
j = len(right) - 1
for value in left:
while j >= 0 and value > limit // right[j]:
j -= 1
if j < 0:
break
count += j + 1
return count
low, high = 1, LIMIT
while low < high:
middle = (low + high) // 2
if count_not_greater(middle) >= rank:
high = middle
else:
low = middle + 1
print(low)复杂度
设两边乘积数为
总结
乘法闭包看似无限，但答案上界让每组可枚举；折半后再二分秩是核心组合。