Codeforces Round #828 (Div. 3)

E1. Divisible Numbers (easy version)

https://codeforces.com/contest/1744/problem/E1

E2. Divisible Numbers (hard version)

https://codeforces.com/contest/1744/problem/E2

4 seconds / 256 megabytes

standard input / standard output

### Problem

You are given $4$ positive integers $a$, $b$, $c$, $d$ with $a < c$ and $b < d$. Find any pair of numbers $x$ and $y$ that satisfies the following conditions:

• $a < x \leq c$, $b < y \leq d$,
• $x \cdot y$ is divisible by $a \cdot b$.

Note that required $x$ and $y$ may not exist.

### Input

The first line of the input contains a single integer $t$ ($1 \leq t \leq 10$), the number of test cases.

The descriptions of the test cases follow.

E1: easy version

The only line of each test case contains four integers $a$, $b$, $c$ and $d$ ($1 \leq a < c \leq 10^5$, $1 \leq b < d \leq 10^5$).

E2: hard version

The only line of each test case contains four integers $a$, $b$, $c$ and $d$ ($1 \leq a < c \leq 10^9$, $1 \leq b < d \leq 10^9$).

### Output

For each test case print a pair of numbers $a < x \leq c$ and $b < y \leq d$ such that $x \cdot y$ is divisible by $a \cdot b$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

### Example

E1: easy version

input

5
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66

output

2 2
4 6
12 12
-1 -1
-1 -1

E2: hard version

input

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

output

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

### E1 题解

#### 最小的 $y$ 的求法

$$x \cdot y = k \cdot a \cdot b$$

$$y=\frac{k\cdot a\cdot b}{x}$$

$$k=\frac{x}{\gcd(a\cdot b,x)}$$

$$y=\frac{a\cdot b}{\gcd(a\cdot b,x)}$$

#### 代码

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$
void solve()
{
ll a, b, c, d;
cin >> a >> b >> c >> d;
for (ll x = a + 1; x <= c; x++)
{
ll y = a * b / __gcd(a * b, x); // 计算最小的y
y *= b / y + 1; // 将y扩大
if (y <= d)
{
cout << x << ' ' << y << endl;
return;
}
}
cout << -1 << ' ' << -1 << endl;
return;
}

### E2 题解

#### 拆分方式

$$x=i\cdot j,\ y=\frac{a\cdot b}{i\cdot j}.$$

#### 代码

• 时间复杂度：$O(\log_2^2n)$
• 空间复杂度：$O(\log_2n)$
void solve()
{
ll a, b, c, d;
cin >> a >> b >> c >> d;
vector<ll> fact_a, fact_b;
for (ll i = 1; i * i <= a; i++)
{
if (!(a % i))
{
fact_a.push_back(i);
if (a / i != i)
fact_a.push_back(a / i);
}
}
for (ll i = 1; i * i <= b; i++)
{
if (!(b % i))
{
fact_b.push_back(i);
if (b / i != i)
fact_b.push_back(b / i);
}
}
for (auto i : fact_a)
{
for (auto j : fact_b)
{
ll p = i * j, q = a * b / (i * j);
ll x = (a / p + 1) * p, y = (b / q + 1) * q;
if (x <= c && y <= d)
{
cout << x << ' ' << y << endl;
return;
}
x = (a / q + 1) * q, y = (b / p + 1) * p;
if (x <= c && y <= d)
{
cout << x << ' ' << y << endl;
return;
}
}
}
cout << -1 << ' ' << -1 << endl;
return;
}