2020牛客暑期多校训练营（第三场）F、Fraction Construction Problem（数论、exgcd）

题目链接

题面：

题意：
给定 $a,b$a,b
求解：
$\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$dc​−fe​=ba​

其中
d<b and f<b
$1\le c,e\le 4e12$1≤c,e≤4e12

如果无解输出 $-1-1-1-1$−1 −1 −1 −1

题解1：
通分后有 $\frac{cf-ed}{df}=\frac{a}{b}$dfcf−ed​=ba​，那么有 $k\ast df=b,k\ast (df-ed)=a$k∗df=b,k∗(df−ed)=a
我们猜测 $d,f$d,f为 $b$b的因子，然后用扩展exgcd求解。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxp=1100;
const int maxm=100100;
const int up=100000;

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,x,y);
    ll z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}

bool get(ll a,ll b,ll c,ll &x,ll &y)
{
    ll d=exgcd(a,b,x,y);
    if(c%d) return false;
    x=x*c/d,y=y*c/d;
    return true;
}

int cnt;
ll fac[maxn];

void fi(int n)
{
    cnt=0;
    if(n==1) return ;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i) continue;
        fac[++cnt]=i;
        if(i!=1&&i*i!=n) fac[++cnt]=n/i;
    }
}

bool so(void)
{
    ll a,b,now,k,x,y,aa;
    scanf("%lld%lld",&a,&b);
    fi(b);
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            now=1ll*fac[i]*fac[j];
            if(now%b!=0&&b%now!=0) continue;
            if(now<b)
            {
                k=b/now;
                if(a%k) continue;
                aa=a/k;
                if(get(fac[i],-fac[j],aa,x,y))
                {
                    ll cm=abs(min(0ll,min((x-fac[j])/fac[j],(y-fac[i])/fac[i])));
                    x+=fac[j]*cm;
                    y+=fac[i]*cm;
                    printf("%lld %lld %lld %lld\n",x,fac[j],y,fac[i]);
                    return true;
                }
            }
            else
            {
                k=now/b;
                aa=a*k;
                if(get(fac[i],-fac[j],aa,x,y))
                {
                    ll cm=abs(min(0ll,min((x-fac[j])/fac[j],(y-fac[i])/fac[i])));
                    x+=fac[j]*cm;
                    y+=fac[i]*cm;
                    printf("%lld %lld %lld %lld\n",x,fac[j],y,fac[i]);
                    return true;
                }
            }
        }
    }
    return false;
}

int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        if(!so()) printf("-1 -1 -1 -1\n");
    }
    return 0;
}

题解2：官方题解
①、若 $a,b$a,b不互质：
我们令 $g$g为 $a，b$a，b的一个大于 1 的公因数，那么 $\frac{a}{g}+1,\frac{b}{g},1,\frac{b}{g}$ga​+1,gb​,1,gb​就是答案。

②、如果a，b互质且b的相异质因数超过1个：
先找到 $d,f$d,f，其中 $d\ast f=bandgcd(d,f)=1$d∗f=b and gcd(d,f)=1

通分后得到 $\frac{cf-ed}{df}=\frac{a}{b}$dfcf−ed​=ba​，也就是找到 c 和 e 满足 $c\ast f-e\ast d=a$c∗f−e∗d=a，由于 $gcd(d,f)=1$gcd(d,f)=1，该二元一次不定方程一定有解（exgcd）

③、如果a，b互质且b的相异质因数不超过1个：
无解。
假设 $b=p^k$b=pk，由于a，b互质，而且 $\frac{c}{d}-\frac{e}{f}$dc​−fe​化简后必须为 $\frac{a}{b}$ba​，但 $d,f$d,f的质因数分解中 $p$p 的指数都小于k（因为 d<b,f<b）， lcm(d,f)<b且lcm(d,f)∣b，所以不能化为 $\frac{a}{b}$ba​的形式。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=2000100;
const int maxp=1100;
const int maxm=500100;
const int up=100000;

int prime[maxn],cnt=0;
int ha[maxn];

void Prime(void)
{
    ha[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
        {
            ha[i]=i;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&prime[j]*i<maxn;j++)
        {
            ha[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}

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

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,x,y);
    ll z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}

bool get(ll a,ll b,ll c,ll &x,ll &y)
{
    ll d=exgcd(a,b,x,y);
    if(c%d) return false;
    x=x*c/d,y=y*c/d;
    return true;
}

int main(void)
{
    Prime();
    int tt;
    scanf("%d",&tt);
    ll a,b;
    while(tt--)
    {
        scanf("%lld%lld",&a,&b);
        ll gc=gcd(a,b);
        a/=gc,b/=gc;
        if(gc!=1)
        {
            printf("%lld %lld %lld %lld\n",a+1,b,1ll,b);
            continue;
        }

        ll d=1,f=b;
        while(f>1&&f%ha[b]==0)
        {
            d*=ha[b];
            f/=ha[b];
        }
        if(f==1)
        {
            printf("-1 -1 -1 -1\n");
            continue;
        }
        ll c,e;
        get(f,-d,a,c,e);
        ll k=abs(min(0ll,min((c-d)/d,(e-f)/f)));
        c+=k*d;
        e+=k*f;
        printf("%lld %lld %lld %lld\n",c,d,e,f);

    }
    return 0;
}