2020牛客暑期多校训练营（第三场） F Fraction Construction Problem
Fraction Construction Problem
https://ac.nowcoder.com/acm/contest/5668/F
题目大意
有t(1≤t≤105)次查询，每个查询给出两个正整数a,b（a，b≤2×106）。
输出一组满足以下条件的四个正整数c,d,e,f：
输出一组满足以下条件的四个正整数c,d,e,f：
如果没有解决方案，输出“ -1 -1 -1 -1”。
解题思路
进行赛后冷静分析，可以归纳出三种情况，这三种情况只需在代码中依次判断：
情况一：b=1或者b是质数时，一定无解。这种情况很好理解。
情况二：gcd(a,b)!=1时，求出g=gcd(a,b)，一定存在一组解：c=a/g+1，d=b/g，e=1，f=b/g。
情况二：gcd(a,b)!=1时，求出g=gcd(a,b)，一定存在一组解：c=a/g+1，d=b/g，e=1，f=b/g。
情况三：当gcd(a,b)=1，即ab互质时，因为这里b不是质数，可以分成两个相异质因数--d,f，所以要以b=df且d,f互质的条件找到d,f。
寻找2到sqrt(b)的素数，找出第一个被b整除的素数i，然后将f赋值为b/i。
接下来要开始求出c,e。已知b=df，所以根据原方程可得a=c×f−e×d,求解c和e，就能用扩展欧几里得算法来求解c,e。
在求出c和e之后要判断一下正负，通过c和e的正负性判断两个相异质因数分别对应谁。
在求出c和e之后要判断一下正负，通过c和e的正负性判断两个相异质因数分别对应谁。
AC代码
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
long long s=exgcd(b,a%b,x,y),t=x;
x=y,y=t-(a/b)*y;
return s;
}
int main()
{
int a,b,g,i,j;
long long c,d,e,f,t,x;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
g=gcd(a,b);
if(g>1)
{
printf("%d %d %d %d\n",a/g+1,b/g,1,b/g);
continue;
}
d=f=0;
for(i=2;i*i<=b;i++)
if(b%i==0 && gcd(i,b/i)==1)
{
d=i,f=b/i;
break;
}
if(d==0 && f==0)
{
printf("-1 -1 -1 -1\n");
continue;
}
c=e=0;
x=exgcd(f,d,c,e);
c*=a,e*=a;
if(c>0 && e<0) printf("%lld %lld %lld %lld\n",c,d,-e,f);
else printf("%lld %lld %lld %lld\n",e,f,-c,d);
}
} 2020牛客暑期多校训练营 文章被收录于专栏
只是题解，可参考，可学习，可点赞:)
领导捞捞我
查看4道真题和解析