数论2

题目来源：https://ac.nowcoder.com/acm/contest/5668/F

题意：c/d-e/f=a/b,这里给出a，b，求可行的c，d，e，f（这里要求d与f值小于b）

解题思路：这是一道数论题，需要一定的数学知识去将这个问题转化为我们熟悉的问题。先通分变为（cf-be）/df=a/b，再假设a1/b1为a/b的最简化的分数。具体验证方法如下： 。
所以问题转化为一个求b的互质因子问题。再一个大的范围内求出第一个被b整除的质数d，然后求f

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a , b , sizeof(a))
const int N = 200005;
int prime[N],p;
bool is_prime[N];
 typedef long long ll;
void init()
{
    for(int i=2;i<N;++i)
    {
        if(!is_prime[i]) 
        prime[++p]=i;
        for(int j=1;j<=p&&prime[j]*i<N;++j)
        {
            is_prime[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}

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

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

ll solve_ex_gcd(ll a, ll b, ll c, ll &x, ll &y)
{
    ll inv = gcd1(a, b, x, y);
    if(c % inv)
    {
        x = -1;
        y = -1;
        return -1;
    }
    x *= (c / inv);
    y *= (c / inv);
    return 0;
}


void solve()
{
    ll a, b;
    cin >> a >> b;
    ll k = gcd(a, b);
    if(k != 1)
    {
        a /= k;b /= k;
       cout<<a+1<<1<<b<<1<<endl;
        return ;
    }

    if(b == 1 || is_prime[b]==0) 
    puts("-1 -1 -1 -1");
    else             
    {
        ll tmp = 0, time = 0;                
        ll bb = b;
        for(int i = 1;i <= p && bb != 1; i++)  //找两个质因数。 
        {
            if(bb % prime[i] == 0)
            {
                tmp=prime[i];
                while(bb % prime[i] == 0) 
                time++,bb /= prime[i];
                break;
            }
        }

        if(bb == 1)
        {puts("-1 -1 -1 -1");return ;}
        ll d = 1;
        for(int i = 1;i <= time; i++) d *= tmp;
        ll f = bb;
        ll c = 0, e = 0;
        solve_ex_gcd(f, d, a, c, e);
        if(c < 0 && e > 0) 
        cout << e << " " << f << " " << -c << " " << d << endl;
        else 
        cout << c << " " << d << " " << -e << " " << f << endl;
    }
}

int main()
{
    init();
    int q;
    cin>>q;
    while(q--) 
    solve();
}