#P3818. 第1题-非空子序列
-
2000ms
Tried: 8
Accepted: 5
Difficulty: 6
所属公司 :
阿里
时间 :2025年9月27日-阿里淘天
-
算法标签>数论构造
第1题-非空子序列
解题思路
给定互不相同的正整数数组 a1…an,要把所有元素分到两个非空数组 b 与 c 中,使得:
对 b 的任意非空子序列 d 与 c 的任意非空子序列 e,d 中所有元素的乘积都不是e 中所有元素的乘积的整数倍。
关键观察
若存在某个素数 p,使得 c 中的每个数都含有素因子 p,而 b 中的所有数都不含素因子 p,则任取 d ⊆ b、e ⊆ c:
e的乘积一定含有素因子p;d的乘积不含素因子p; 因此d的乘积不可能是e的乘积的整数倍。 只要能找到这样的p并据此分组,就满足题意。
构造策略(总能成功)
-
用最小素因子筛(SPF)在
1e6范围内预处理质因数分解。 -
对每个数分解出互异素因子集合,统计每个素数
p出现于多少个元素中(记cnt[p])。 -
若存在素数
p使得0 < cnt[p] < n:- 令
c = { 所有能被 p 整除的数 },b = 其余。 - 此时两组均非空,且满足上面的充分必要条件,直接输出。
- 令
-
否则,对所有出现过的素数
p都有cnt[p] = n,即所有数拥有相同的素因子集合(仅指数可能不同)。- 取数组中的最小值
m单独放入b,其余元素放入c。 - 证明要点:对任意
y ∈ c,必存在某个素数在y中的指数严格大于在m中的指数(否则将有y | m且y < m,与“m为最小值”矛盾)。 于是对任何e ⊆ c,其乘积在该素数上的指数 ≥y的指数 >m的指数,故b的乘积(即m)不可能是e的乘积的整数倍。 - 两组非空(
n ≥ 2),性质成立。
- 取数组中的最小值
示例中的“奇偶分组”(把奇数放
b、偶数放c)正是第 3 步在p=2时的特例。
实现要点
- 预筛
spf[x]为x的最小素因子,分解时不断除以spf[x]并去重即可得到互异素因子集合。 - 统计时仅对实际出现的素数计数,并把这些素数存入列表,便于用例结束时快速清理或遍历(避免
O(1e6)的全量清空)。 - 输出任一合法解即可:先输出
b的长度与元素,再输出c的长度与元素。
复杂度分析
- 预处理 SPF:
O(MAX log log MAX),MAX = 1e6。 - 单个数分解:均摊
O(log a_i)(按素因子个数计)。 - 单个用例:
O(n log MAX)时间,O(n + #primes)空间(存数组与本用例出现过的素数集合)。
代码实现
Python
import sys
# 预处理最小素因子 SPF
MAXA = 10**6
spf = list(range(MAXA + 1))
for i in range(2, int(MAXA ** 0.5) + 1):
if spf[i] == i:
step = i
start = i * i
for x in range(start, MAXA + 1, step):
if spf[x] == x:
spf[x] = i
def factor_distinct_primes(x):
"""分解x的不同素因子,使用spf并去重"""
res = []
while x > 1:
p = spf[x]
res.append(p)
while x % p == 0:
x //= p
# 去重(spf保证递增)
uniq = []
last = -1
for v in res:
if v != last:
uniq.append(v)
last = v
return uniq
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
T = next(it)
out_lines = []
for _ in range(T):
n = next(it)
arr = [next(it) for __ in range(n)]
# 统计每个素数出现次数
cnt = {}
primes_of = [] # 每个数的素因子集合
used_primes = [] # 本用例出现过的素数(用于遍历)
for v in arr:
ps = factor_distinct_primes(v)
primes_of.append(ps)
for p in ps:
if p not in cnt:
cnt[p] = 0
used_primes.append(p)
cnt[p] += 1
# 尝试找到 0 < cnt[p] < n 的素数
chosen = -1
for p in used_primes:
c = cnt[p]
if 0 < c < n:
chosen = p
break
b, c = [], []
if chosen != -1:
# c 为能被 chosen 整除的数,b 为其余
for v in arr:
if v % chosen == 0:
c.append(v)
else:
b.append(v)
else:
# 所有素数都整除所有数:选最小值入 b,其余入 c
mn = min(arr)
b = [mn]
c = [v for v in arr if v != mn]
# 输出
out_lines.append(str(len(b)))
out_lines.append(" ".join(map(str, b)) if b else "")
out_lines.append(str(len(c)))
out_lines.append(" ".join(map(str, c)) if c else "")
sys.stdout.write("\n".join(out_lines))
if __name__ == "__main__":
solve()
Java
import java.io.*;
import java.util.*;
/* ACM 风格:主类名 Main,读入输出在 main,核心逻辑放外部函数 */
public class Main {
static final int MAXA = 1000000;
static int[] spf = new int[MAXA + 1];
// 预处理最小素因子
static void sieve() {
for (int i = 0; i <= MAXA; i++) spf[i] = i;
for (int i = 2; i * i <= MAXA; i++) {
if (spf[i] == i) {
for (int x = i * i; x <= MAXA; x += i) {
if (spf[x] == x) spf[x] = i;
}
}
}
}
// 分解为不同素因子(升序且去重)
static ArrayList<Integer> factorDistinctPrimes(int x) {
ArrayList<Integer> ps = new ArrayList<>();
while (x > 1) {
int p = spf[x];
ps.add(p);
while (x % p == 0) x /= p;
}
return ps; // 已去重
}
public static void main(String[] args) throws Exception {
sieve();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder out = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
while (T-- > 0) {
// 读 n
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
// 读数组
int[] a = new int[n];
int idx = 0;
while (idx < n) {
st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens() && idx < n) {
a[idx++] = Integer.parseInt(st.nextToken());
}
}
// 统计每个素数出现次数
HashMap<Integer, Integer> cnt = new HashMap<>();
ArrayList<ArrayList<Integer>> primesOf = new ArrayList<>(n);
ArrayList<Integer> used = new ArrayList<>();
for (int v : a) {
ArrayList<Integer> ps = factorDistinctPrimes(v);
primesOf.add(ps);
for (int p : ps) {
Integer c = cnt.get(p);
if (c == null) {
cnt.put(p, 1);
used.add(p);
} else {
cnt.put(p, c + 1);
}
}
}
int chosen = -1;
for (int p : used) {
int c = cnt.get(p);
if (0 < c && c < n) {
chosen = p;
break;
}
}
ArrayList<Integer> b = new ArrayList<>();
ArrayList<Integer> c = new ArrayList<>();
if (chosen != -1) {
for (int v : a) {
if (v % chosen == 0) c.add(v);
else b.add(v);
}
} else {
int mn = a[0];
for (int v : a) mn = Math.min(mn, v);
b.add(mn);
for (int v : a) if (v != mn) c.add(v);
}
// 输出:先 b,再 c
out.append(b.size()).append('\n');
for (int i = 0; i < b.size(); i++) {
if (i > 0) out.append(' ');
out.append(b.get(i));
}
out.append('\n');
out.append(c.size()).append('\n');
for (int i = 0; i < c.size(); i++) {
if (i > 0) out.append(' ');
out.append(c.get(i));
}
out.append('\n');
}
System.out.print(out.toString());
}
}
C++
#include <bits/stdc++.h>
using namespace std;
/* ACM 风格:主函数读入输出,外部函数实现核心逻辑 */
const int MAXA = 1000000;
int spf[MAXA + 1]; // 最小素因子
// 预处理最小素因子
void sieve() {
for (int i = 0; i <= MAXA; ++i) spf[i] = i;
for (int i = 2; i * i <= MAXA; ++i) {
if (spf[i] == i) {
for (int x = i * i; x <= MAXA; x += i) {
if (spf[x] == x) spf[x] = i;
}
}
}
}
// 分解不同素因子(已去重且升序)
vector<int> factorDistinctPrimes(int x) {
vector<int> ps;
while (x > 1) {
int p = spf[x];
ps.push_back(p);
while (x % p == 0) x /= p;
}
return ps;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve();
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
unordered_map<int,int> cnt; cnt.reserve(n*2);
vector<vector<int>> primesOf(n);
vector<int> used;
// 统计素数出现次数
for (int i = 0; i < n; ++i) {
primesOf[i] = factorDistinctPrimes(a[i]);
for (int p : primesOf[i]) {
auto it = cnt.find(p);
if (it == cnt.end()) {
cnt.emplace(p, 1);
used.push_back(p);
} else {
it->second++;
}
}
}
int chosen = -1;
for (int p : used) {
int c = cnt[p];
if (0 < c && c < n) { chosen = p; break; }
}
vector<int> b, c;
if (chosen != -1) {
for (int v : a) {
if (v % chosen == 0) c.push_back(v);
else b.push_back(v);
}
} else {
int mn = *min_element(a.begin(), a.end());
b.push_back(mn);
for (int v : a) if (v != mn) c.push_back(v);
}
// 输出:先 b 再 c
cout << (int)b.size() << "\n";
for (int i = 0; i < (int)b.size(); ++i) {
if (i) cout << ' ';
cout << b[i];
}
cout << "\n";
cout << (int)c.size() << "\n";
for (int i = 0; i < (int)c.size(); ++i) {
if (i) cout << ' ';
cout << c[i];
}
cout << "\n";
}
return 0;
}
题目内容
给定一个长度为 n 的数组 {a1,a2,…,an}(元素互不相同)。你需要将所有元素分到两个最初为空的数组 b 与 c 中,使得:
-
数组 b 与 c 均为非空数组;
-
对于数组 b 的任意非空子序列 d={di,…,dx} 与数组 c 的仼意非空子序列 e={e1,…,ey},都有 ∏i=1xdi 不是 ∏j=1yej 整数倍。
请输出任意一组满足条件的数组 b 与 c ,可以证明在题目限制中恒有解。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104) 代表数据组数,每组测试数据描述如下:
-
第一行输入一个整数 n(2≦n≦2×105),表示数组长度;
-
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦106) ,表示数组元素,题目保证数组中元素互不相同。
除此之外,保证单个测试文件的 n 之和不超过 2×105 。
输出描述
对于每一组测试数据,依次输出四行:
-
第一行输出一个整数,表示数组 b 的长度;
-
第二行输出该长度个整数,表示数组 b 的元素;
-
第三行输出一个整数,表示数组 c 的长度;
-
第四行输出该长度个整数,表示数组 0 的元素。
若存在多种合法划分,输出任意一种即可。若存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。
样例1
输入
2
4
2 3 1 4
6
2 3 4 9 25
输出
2
1 3
2
2 4
3
3 9 25
2
2 4