链接

https://ac.nowcoder.com/acm/contest/5668

题意

已知 a , b ( a , b ≤ 2 × 1 0 6 ) a,b(a,b\le2\times10^6) a,b(a,b≤2×106)

求 $c,d,e,f$ 满足一下要求

• c d − e f = a b \frac{c}{d}-\frac{e}{f}=\frac{a}{b} dc​−fe​=ba​
• $d<b,f<b$
• 1 ≤ c , e ≤ 4 × 1 0 12 1\le c,e\le 4\times10^{12} 1≤c,e≤4×1012

思路

设$g=gcd(a,b)$

情况一：$g\ne 1$

a b \frac{a}{b} ba​ 的最简形式为 a / g b / g \frac{a/g}{b/g} b/ga/g​，根据最简分数的唯一性可得 $d=b/g,e=b/g,c-e=a/g$，另 $e=1$，所以 $c=a/g+1$

情况二：$g=1$

• b的不同的质因数的个数小于 $1$

  无解

  设 b = p k b=p^k b=pk，因为 $g=1$，所以 a b \frac{a}{b} ba​ 就是最简分数，那么 c d − e f \frac{c}{d}-\frac{e}{f} dc​−fe​ 的最简形式就是 a b \frac{a}{b} ba​，又因为 $d<b,f<b$，所以 $d$ 和 $f$ 中质因数 $p$ 的个数都小于 $k$，所以不成立

• b的不同的质因数的个数大于 $1$

  另 $d\ast f=b$ 且 $gcd(d,f)=1$，用扩展欧几里得算法求解 $cf-ed=a$

代码

#include
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define int long long
using namespace std;
typedef double DB;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=2e6+5;
int m,p[N],mn[N];  //mn[i] 为 i的最小质因数
void Euler_seive(int n) {  //注意筛后 mn[1]=0for(int i=2;i<=n;i++) {if(mn[i]==0) mn[i]=i,p[++m]=i;for(int j=1;j<=m;j++) {if(p[j]>mn[i]||p[j]*i>n) break;mn[i*p[j]]=p[j];}}
}
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
int exgcd(int a,int b,int &x,int &y) {if(b==0) {x=1;y=0;return a;}int ret=exgcd(b,a%b,x,y);int z=x;x=y;y=z-(a/b)*y;return ret;
}
int get(int x) {if(mn[x]==x||x==1) return x;int ret=1;int t=x;while(t%mn[x]==0) t/=mn[x],ret*=mn[x];return ret;
}
signed main() {Euler_seive(2000000);int T;scanf("%lld",&T);while(T--) {int a,b;scanf("%lld%lld",&a,&b);int c,d,f,e;int g=gcd(a,b);if(g!=1) printf("%lld %lld %lld %lld\n",a/g+1,b/g,1,b/g);else {f=get(b);if(f==b) puts("-1 -1 -1 -1");else {d=b/f;g=exgcd(f,d,c,e);if(c<0) printf("%lld %lld %lld %lld\n",e*a,f,-c*a,d);else printf("%lld %lld %lld %lld\n",c*a,d,-e*a,f);}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！