首页
题库
训练
比赛
作业
讨论
排名
登录
Language
English
한국어
简体中文
正體中文
1 条题解
0
DHEnry
SU
@
2026-11-15 22:53:17
T4 数学家猫猫
首先注意到,操作中的
min
\min
min
相当于直接删除较大的数,不影响较小的数;而
gcd
\gcd
g
cd
操作得到的新数一定不大于原来两个数的最小值。因此,不论如何选择
min
\min
min
或
gcd
\gcd
g
cd
,最终留下的数一定等于原数组某个非空子集的
gcd
\gcd
g
cd
。
因此,问题转化为:统计原数组所有非空子集的
gcd
\gcd
g
cd
,共有多少种不同的值。
具体做法:
对每个
A
_
i
A\_i
A
_
i
分解所有因数。
对每个因数
d
d
d
,记录哪些
A
_
i
A\_i
A
_
i
是
d
d
d
的倍数。
枚举每个因数
d
d
d
,对所有是
d
d
d
的倍数的
A
_
i
A\_i
A
_
i
求
gcd
\gcd
g
cd
,若结果恰好等于
d
d
d
,则
d
d
d
是一个可能的最终答案。
时间复杂度:
O
(
n
a
_
i
log
a
_
i
)
O(n \sqrt{a\_i} \log a\_i)
O
(
n
a
_
i
lo
g
a
_
i
)
,因为对每个数分解因数,并在检查时对相关数求一次
gcd
\gcd
g
cd
。
View all 1 solutions
数学家猫猫
查看题目
登录后递交
讨论
题解
文件
统计
信息
ID
225
时间
1000ms
内存
512MiB
难度
4
标签
数论
梦熊联盟
梦熊二十连测
2025
递交数
1
已通过
1
上传者
DHEnry
关闭
登录
使用您的 Hydro 通用账户
使用 FMCRAFT 登录
忘记密码或者用户名?