题目链接

Codeforces Round #828 (Div.3)

Divisible Numbers (hard version)

题目描述

给出四个整数 \(a, b, c, d\), 请你构造一对整数 \((x, y)\), 满足：

• \(a < x\leq c\), \(b<y\leq d\)

• \(x\times y\) 是 \(a \times b\) 的倍数

若不存在，输出 \(-1\)

数据范围：

简单版：\(1\leq a < c \leq 10^5, 1\leq b<d\leq 10^5\)

困难版：\(1\leq a < c \leq 10^9, 1\leq b<d\leq 10^9\)

其中，单个测试点中包含不超过 \(10\) 组数据

样例 #1

样例输入 #1

10
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
1024 729 373248 730
1024 729 373247 730
5040 40320 40319 1000000000
999999999 999999999 1000000000 1000000000
268435456 268435456 1000000000 1000000000

样例输出 #1

2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912

解题思路

思维

简单版主要是枚举 \(x\)，然后要使 \(x\times y\) 是 \(a\times b\) 的倍数，则 \(y\) 应该是 \(a\times gcd(a\times b,x)\) 的倍数，然后范围内判断是否存在这样的倍数即可，困难版由于数据范围的原因不能直接枚举 \(x\)，观察可知：\(y\) 要是 \(a\times gcd(a\times b,x)\) 的倍数，这里 \(gcd(a\times b,x)\) 一定是 \(a\times b\) 的约数，只用枚举约数即可，然后即可解出 \(y\)，同理，解出 \(y\) 后同样的方法解出 \(x\)

• 时间复杂度：\(O(1600\times 1600\times log(10^9))\)