Codeforces Round #828 (Div. 3) E2 // 数论 + dfs

题目来源：Codeforces Round #828 (Div. 3) E2 - Divisible Numbers

题目链接：Problem - E2 - Codeforces

题意

有 \(t\) 组案例（\(1\ \le t \le 10\)），对于每个案例：给定四个整数\(a,b,c,d\)（\(1 \le a < c \le 10^9,1 \le b < d \le 10^9\)），求一组整数\(x,y\)，满足\(a < x \le c\)，\(b < y \le d\)，\(ab\ |\ xy\)，若不存在，则输出\(-1\ -1\)。

思路：数论 + dfs

由\(ab\ |\ xy\)可知，存在整数\(res_1,res_2\)满足：\(res_1·res_2 = ab, res_1\ |\ x, res_2\ |\ y\)，即\(res_1,res_2\)为\(ab\)的因数，\(x\)为\(res_1\)的倍数，\(y\)为\(res_2\)的倍数。

于是有如下做法：

1. 先对\(ab\)分解质因数
2. 再dfs枚举\(ab\)的第一个因数\(res_1\)，则\(res_2 = \large \frac{ab}{res_1}\)
3. 由于\(a < x \le c\)，\(b < y \le d\)，于是先找出大于 \(a\) 的最小的 \(res_1\) 的倍数，以及大于 \(b\) 的最小的 \(res_2\) 的倍数，即令\(x = {\large \lceil \frac{a + 1}{res_1} \rceil} ·res_1 = {\large \lfloor \frac{a + 1 + res_1 - 1}{res_1} \rfloor} ·res_1\) ，\(y = {\large \lceil \frac{b + 1}{res_2} \rceil} ·res_2 = {\large \lfloor \frac{b + 1 + res_2 - 1}{res_2} \rfloor} ·res_2\)，若求出的值满足：\(x \le c\)，\(y \le d\)，则说明成功找出一组解。

记 \(ab\) 的因数个数为 \(\omega\)，由于 \([1,10^{18}]\) 范围内的数的因数个数最多为\(103680\)，因此有\(\omega \le 103680\)。
时间复杂度：\(O(t·(\sqrt{a}+\sqrt{b}+\omega))\).

代码

#include <bits/stdc++.h>
#define endl '\n'
#define LL long long
#define PII pair<int,int>
using namespace std;

int a, b, c, d;
map<int, int> mp;
vector<PII> v;
bool ok;

void getPrimes(int x)
{
    for(int i = 2; i <= x / i; ++ i) {
        while(x % i == 0) ++ mp[i], x /= i;
    }
    if(x > 1) ++ mp[x];
}

void dfs(int u, LL res)
{
    if(ok) return;
    if(u == v.size()) {
        LL res2 = (LL)a * b / res;
        LL x = (a + 1 + res - 1) / res * res, y = (b + 1 + res2 - 1) / res2 * res2;
        if(x <= c && y <= d) {
            cout << x << " " << y << endl;
            ok = true;
        }
        return;
    }
    LL mul = 1;
    for(int i = 0; i <= v[u].second; ++ i) {
        dfs(u + 1, res * mul);
        mul *= v[u].first;
    }
}

void solve()
{
    cin >> a >> b >> c >> d;

    mp.clear();
    getPrimes(a), getPrimes(b);

    v.clear();
    for(auto p : mp) v.push_back(p);

    ok = false;
    dfs(0, 1);
    if(!ok) cout << -1 << " " << -1 << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}