F-Fraction Construction Problem（数学、拓展欧几里得算法）

题目链接：https://ac.nowcoder.com/acm/contest/5668/F
简要题意：

解题思路：
状况1：a和b不互质，设其最大公因子是a/g + 1,b/g,1,b/g即是答案。
状况2：a,b互质，且b的质因子数不超过1，无解。

状况3：a,b互质，且相异质因子数超过1个：

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2e6+7;

int prime[MAXN], cnt;
bool vis[MAXN];
int mp[MAXN];
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) {x = 1; y = 0; return a;}
    ll d = exgcd(b, a%b, y, x);
    y = y - a/b * x;
    return d;
}
void Prime()
{
    for(int i = 2; i <= MAXN; i++) {
        if(!vis[i]) {
            prime[++cnt] = i;
            mp[i] = i;
        }
        for(int j = 1; j <= cnt ; j++) {
            if(i * prime[j] > MAXN) break;
            vis[i * prime[j]] = 1;
            mp[i * prime[j]] = prime[j];
            if(i % prime[j] == 0) break;    //当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。 
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    Prime();
    while(t--)
    {
        ll a, b;
        scanf("%lld%lld",&a,&b);
        if(b == 1)
        {
            printf("-1 -1 -1 -1\n");
            continue;
        }
        ll g = __gcd(a, b);
        if(g != 1)
        {
            printf("%lld %lld %lld %lld\n",a/g+1,b/g,1ll,b/g);
        }
        else
        {
            ll f, d = b;
            while(d % mp[b] == 0) d/=mp[b];
            f = b/d;     
            if(d == 1) printf("-1 -1 -1 -1\n");
            else
            {
                ll c, e;
                exgcd(f, d, c, e);
                c = (c % d + d) % d;    //固定方法，看到的时候再回忆一遍
                e = -(1-c*f)/d;
                c *= a;
                e *= a;
                printf("%lld %lld %lld %lld\n",c,d,e,f);
            }
        }
    }
}