题意： 给定，求出满足的任意一组。
数据范围：，，且

题解： 通分得到：，那么自然会考虑到分子分母对应相等解决。

  • 当，令，此时
    这时候，故直接令，
    那么可以构造出
  • ，那么此时需要分解成两个互质的部分，且均不为，否则判
    那么预处理内的质数，并处理出每个数的最小质因子，就可以分解了。
    分解成功后进行[](https://blog.csdn.net/weixin_43900869/article/details/106959343) 即可。
    这里有个技巧，由于是进行，我们可以变成，然后得到后再取反即可。注意最后的答案必须是正数，且扩大倍，这也是最大范围的原因。
  • 代码： 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int pri[N], cnt;
int Mipri[N];
bool st[N];
void xs(int n) {
    st[0] = st[1] = true;
    Mipri[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!st[i]) pri[cnt++] = i, Mipri[i] = i;
        for(int j = 0; j < cnt && 1ll * i * pri[j] <= n; j++) {
            Mipri[i * pri[j]] = pri[j];
            st[i * pri[j]] = true;
            if(i % pri[j] == 0) break;
        }
    }
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void exgcd(ll a, ll b, ll &x, ll &y) {
    if(!b) {
        x = 1, y = 0; 
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int main()
{
    xs(N - 1);
    int T; scanf("%d", &T);
    while(T--) {
        int a, b;
        scanf("%d%d", &a, &b);

        int g = gcd(a, b);
        if(g > 1) {
            int f = 1, e = 1, d = b / g, c = (a + b) / g;
            printf("%d %d %d %d\n", c, d, e, f);
            continue;
        }

        ll f = 1, d = b, p = Mipri[b];
        while(p > 1 && d % p == 0) d /= p, f *= p;
        if(d == 1) {
            puts("-1 -1 -1 -1");
            continue;
        }

        ll c, e;
        exgcd(d, f, e, c);
        e = -e;

        if(e <= 0 || c <= 0) {
            ll e1 = (e % f + f) % f;
            ll c1 = (c % d + d) % d;
            ll cnt = max(0ll, max((e1 - e) / f, (c1 - c) / d));
            e += f * cnt, c += d * cnt;
        }
        e *= a, c *= a;
        printf("%lld %lld %lld %lld\n", c, d, e, f);
    }
    return 0;
}