把质数拆成两组生成所有乘积，二分答案并双指针统计不超过它的乘积对数。
OJ: codeforces
题目 ID: 912E
难度:省选/NOI-
标签:Meet-in-the-Middle二分答案数论python
创建: 2026-07-16 20:10
更新: 2026-10-28 17:33
题意
给定至多 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++。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-02
* update_at: 2026-08-02
*/
/* CF912E Prime Gift */
/* 把质数交错分成两组，DFS 枚举 <= 1e18 的所有乘积；二分答案 limit，
* 用只向左移动的右指针统计 left[i]*right[j] <= limit 的配对数。 */
#include <bits/stdc++.h>
using namespace std;
const long long LIMIT = 1000000000000000000LL; // 1e18
int n; // 质数个数（<= 16）
long long k; // 第 k 小
long long primes[20];
vector<long long> left_vals, right_vals; // 两组的所有乘积（升序）
// 枚举 selected 中质数的幂乘积，value 不超过 LIMIT
void dfs(vector<long long> &out, const vector<long long> &selected,
int index, long long value) {
if (index == (int)selected.size()) {
out.push_back(value);
return;
}
long long p = selected[index];
while (value <= LIMIT) {
dfs(out, selected, index + 1, value);
if (value > LIMIT / p)
break; // 乘下一个 p 会超过 LIMIT
value *= p;
}
}
// 统计乘积 <= limit 的对数
long long count_not_greater(long long limit) {
long long count = 0;
int j = (int)right_vals.size() - 1;
for (long long v : left_vals) {
while (j >= 0 && v > limit / right_vals[j])
j--; // 用除法避免溢出：v * right > limit 等价于 v > limit / right
if (j < 0)
break;
count += j + 1;
}
return count;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++)
cin >> primes[i];
cin >> k;
// 交错拆分：小的质数尽量分到两边，让乘积数平衡
vector<long long> a, b;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
a.push_back(primes[i]);
else
b.push_back(primes[i]);
}
dfs(left_vals, a, 0, 1);
dfs(right_vals, b, 0, 1);
sort(left_vals.begin(), left_vals.end());
sort(right_vals.begin(), right_vals.end());
// 二分答案：第一个 count_not_greater(mid) >= k 的 mid
long long low = 1, high = LIMIT;
while (low < high) {
long long mid = (low + high) / 2;
if (count_not_greater(mid) >= k)
high = mid;
else
low = mid + 1;
}
cout << low << '\n';
return 0;
}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)复杂度
设两边乘积数为
总结
乘法闭包看似无限，但答案上界让每组可枚举；折半后再二分秩是核心组合。