首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
最大GCD
2条解析
开通博客写题解
num73
发表于 2020-03-01 20:30:33
由最大公因数的性质:且,易得到结论:对于每一个询问,我们只需在到这个区间中找到一个,使得对任意的成立。 算法1先考虑最朴素的做法:对于每一次询问,求出到这个区间中的每一个数与的最大公因数,并记录最大的那一个。时间复杂度(为最大值),很显然,对于本题的数据规模这个复杂度是不够的。 观察这个题的特点
展开全文
看见我请叫我去学习HA
发表于 2020-03-01 20:16:43
题意:Face 数据范围 Strategy: 看到数据范围可以想到先把1e5以内的因子全部筛一遍, 不要问我为什么比赛的时候没想到,,, 然后pos[i]存i作为因子出现在那些数的下标, 然后每次询问从x的最大因子开始往下走, 询问pos[x_因子]有没有在区间[l, r]中出现过 服了不晓得为啥
展开全文
查看本题
查看本题讨论
相关比赛
4090-牛客练习赛58
进入比赛
5840-牛客练习赛58(重现赛)@oh-my-code
进入比赛
6053-上海理工大学训练赛11
进入比赛
等你来战
查看全部
新疆大学2025年7月月赛(同步赛)
报名截止时间:2025-07-06 18:00
牛客周赛 Round 99
报名截止时间:2025-07-06 21:00
牛客练习赛142
报名截止时间:2025-07-11 21:30
2025年第一届上海师范大学程序设计竞赛(同步赛)
报名截止时间:2025-07-13 18:00
牛客周赛 Round 100
报名截止时间:2025-07-13 21:00
2025牛客暑期多校训练营1
报名截止时间:2025-07-15 17:00
2025牛客暑期多校训练营2
报名截止时间:2025-07-17 17:00
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题