题目 | Divisible Numbers

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\le c$, $b<y\le 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\le t\le 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\le a<c\le {10}^5$, $1\le b<d\le {10}^5$).

E2: hard version

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

Output

For each test case print a pair of numbers $a<x\le c$ and $b<y\le 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 题解

简单版的数据规模为 ${10}^5$，可以考虑 $O(n)$ 级别的做法

算法思路

对于一组 $a$, $b$, $c$, $d$，我们可以在区间 $(a,c]$ 遍历取 $x$，然后再找到满足 $a\cdot b\mid x\cdot y$ 的最小的 $y$ 值。

之所以要找最小的 $y$，是因为除了上面之外还有一个限制条件 $y\in (b,d]$. 若最小的 $y$ 都 $>d$，则可以断言对于这个 $x$，没有满足条件的 $y$；若最小的 $y$ $\le b$，我们可以将 $y$ 扩大到 $\lfloor b/y\rfloor +1$ 倍，若扩大后 $y\le d$ 则可满足；若最小的 $y$ 已经满足条件，则无需其他操作。

如果对于任意 $x$，存在一个 $y$ 满足条件，则输出答案；如果遍历了所有的 $x$ 的情况都没有满足条件的 $y$，则输出 -1 -1.

最小的 $y$ 的求法

由 $a\cdot b\mid x\cdot y$ 得：

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

变形得：

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

又因为 $y$ 要是整数，因此我们要构造一个 $k$，使 $x\mid k\cdot a\cdot b$，由于我们要求最小的 $y$，即我们要求最小的 $k$：

$$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 题解

困难版的数据规模为 ${10}^9$，可以考虑 $O(\log n)$ 级别的做法。

算法思路

我们要求满足 $a\cdot b\mid x\cdot y$ 的 $x\cdot y$，那我们可以直接把 $a\cdot b$ 拆成两个数 $x$ 和 $y$，然后扩大 $x$ 和 $y$ 到符合条件的区间即可，扩大方式和上面一样：$x$ 扩大到 $\lfloor a/x\rfloor +1$ 倍，$y$ 扩大到 $\lfloor b/y\rfloor +1$ 倍。由于我们不确定 $x$ 和 $y$ 的大小关系，因此我们正反都要算一遍。

若存在一组满足条件的 $x$, $y$，则输出答案；若遍历所有的情况后都没有满足条件的 $x$, $y$，则输出 -1 -1.

拆分方式

我们将 $a$ 和 $b$ 的分解因数，然后在 $a$ 的因数中取 $i$，$b$ 的因数中取 $j$，然后我们就可以保证 $i\cdot j\mid a\cdot b$，$\frac{a\cdot b}{i\cdot j}\mid a\cdot b$.

则我们可以令：

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

代码

• 时间复杂度：$O({\log }_2^{2}n)$
• 空间复杂度：$O({\log }_{2}n)$

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;
}