2020牛客暑期多校训练营（第三场）Fraction Construction Problem

2020牛客暑期多校训练营（第三场）Fraction Construction Problem

题解：

(g = gcd(a,b))

• (b==1) 无解

• 首先分析 (g!=1) ，那么就很简单了，(e=0,f=b-1) ，(c=a/g,d=b/g)

• 然后再分析 (g==1) ，对题目给出的式子化简，

  (frac{c}{d}-frac{e}{f}=frac{cf-ed}{df}=frac{a}{b}) ，上面的式子很像 (ax+by=gcd(a,b)) (这个是别人告诉我的) ，所以呢 上式就可以变成 (gcd(f,d)*x) ，所以化简之后的式子就是 ：(frac{x}{lcm(d,f)}=frac{a}{b}) ，因为 (gcd(a,b)=1) ，所以 (lcm(d,f)=b) ，所以 (x=a) ，最后我们可以让 (gcd(d,f)=1) ，(lcm(d,f)=b) 。

  这一步判断有没有解，就是判断b是否有两个不同的素因子，如果有就有解，否则就无解。

• 最后要注意的是把扩展欧几里得的答案转化成正数。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
typedef long long ll;
ll gcd(ll a,ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
int isp[maxn],cnt,v[maxn];
void init() {
    cnt = 0;
    memset(v,0,sizeof(v));
    for (int i = 2; i < maxn; ++i) {
        if (!v[i]) {
            v[i] = i;
            isp[cnt++] = i;
        }
        for (int j = 0; j < cnt; ++j) {
            if (1ll * i * isp[j] >= maxn) break;
            v[i * isp[j]] = isp[j];
        }
    }
}
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (a == 0 && b == 0) return -1;
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extend_gcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
int main() {
    int t;
    init();
    scanf("%d", &t);
    while (t--) {
        ll a, b;
        scanf("%lld%lld", &a, &b);
        if (b == 1) {
            printf("-1 -1 -1 -1
");
            continue;
        }
        ll g = gcd(a, b);
        if (g != 1) {
            printf("%lld %lld %d %lld
", a / g + 1, b / g, 1, b / g);
            continue;
        }
        ll d = b;
        for (int i = 0; i < cnt; i++) {
            while (d % isp[i] == 0) d /= isp[i];
            if (d != b) break;
        }
        ll f = b / d;
        if (d == 1 || f == 1) {
            printf("-1 -1 -1 -1
");
            continue;
        }
        ll c = 0,e = 0;
        ll ans=extend_gcd(f,d,c,e);
        c=(c%d+d)%d;
        e=-(1-c*f)/d;
//        printf("c=%lld e=%lld f=%lld d=%lld ans=%lld
",c,e,f,d,ans);
        c = c*a,e=e*a;
        printf("%lld %lld %lld %lld
",c,d,e,f);
    }
}