社区讨论

一道站外数论分块题

CCoros_Trusds
学术版参与者 7已保存回复 14

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@lo9fr1rd
此快照首次捕获于
2023/10/28 10:41
2 年前
此快照最后确认于
2023/10/28 10:41
2 年前
查看原帖
1s,128MB。
题目大意：
共 TT 组询问，对于每组询问：
给定 a,b,c,da,b,c,d，找到 max⁡ gcd⁡(x,y){a≤x≤b,c≤y≤d}\max~\gcd(x,y)\{a\le x\le b,c\le y\le d\}。
1≤T≤103,1≤a≤b≤109,1≤c≤d≤1091\le T\le10^3,1\le a\le b\le 10^9,1\le c\le d\le 10^9。
题解：
设 gcd⁡(x,y)=k\gcd(x,y)=k，问题转化为：⌊a−1k⌋<⌊bk⌋\left\lfloor\dfrac{a-1}{k}\right\rfloor\lt\left\lfloor\dfrac{b}{k}\right\rfloor 和 ⌊c−1k⌋<⌊dk⌋\left\lfloor\dfrac{c-1}{k}\right\rfloor\lt\left\lfloor\dfrac{d}{k}\right\rfloor 是否成立。
求问为什么能这样转换？

回复

共 14 条回复，欢迎继续交流。

正在加载回复...