题目描述
There are queries.
In each query, you are given two positive integers and
.
Please print a line consists of four positive integers c,d,e,f satisfying the following constraints: ,
and
,
.
If there are multiple solutions, you can print anyone.
If there are no solution, please print -1 -1 -1 -1
in this line.
输入描述
The first line contains one integer
, the number of test cases.
The only line of each test case contains two integers and
.
输出描述
For each test case print four integers . If there are no solution,
should all be
.
示例1
输入
3 4 1 1 6 37 111
输出
-1 -1 -1 -1 1 2 1 3 145 87 104 78
分析
若 ,代表分数
可以约分为
。简便起见,直接令
,那么就有
,有一组解为
,
。
若 ,那么
已经是最简分式,将等式左边通分后,可得
。首先,当
为质数的幂时,无解(文末给出证明)。接下来考虑
有多个不相同质因子的情况。根据算数基本定理,可以将
写成有限个质数的乘积,
。方便起见,直接令
,
。
是一个裴蜀方程,当且仅当
时方程有整数解。若能构造得到的
使得
,那么方程一定有整数解。显然这样的构造方案是存在的,令
,
,就有
。可以用扩展欧几里得算法求得
的特解
,为了满足条件
,不妨让
尽量向
靠近。令
,求一个不等式组即可得到
的上界。有不等式组
,解得
。
接下来给出证明:当 且
为质数的幂次时,无解。
设 ,
,
。由于
是质数的幂次,可设
,
,其中
,
。那么有
且
。很显然,
式的左边分式可以上下同除以
进行约分;又
,故
,这样一来,
就是一个可约分的分式,与事实矛盾。证毕。
代码
/****************************************************************** Copyright: 11D_Beyonder All Rights Reserved Author: 11D_Beyonder Problem ID: 2020牛客暑期多校训练营(第三场)Problem F Date: 8/15/2020 Description: Number Theory, Construction, Extend Euclid Algorithm *******************************************************************/ #include<cstdio> #include<algorithm> #include<iostream> #include<vector> using namespace std; typedef long long ll; const ll top=4000000000000; void ex_gcd(ll,ll,ll&,ll&);//扩展欧几里得算法 vector<int> divide(int);//分解质因数 int main(){ int _; for(cin>>_;_;_--){ int a,b; ll c,d,e,f; scanf("%d%d",&a,&b); int gcd=__gcd(a,b); if(gcd==1){ //互质 vector<int>prime_factor=divide(b); if(prime_factor.size()<=1){ //只有一种质因子 puts("-1 -1 -1 -1"); }else{ ll p=1; while(b%p==0){ p=p*prime_factor.front(); } p/=prime_factor.front(); d=p; f=b/p; ex_gcd(f,d,c,e); c=c*a; e=-e*a; //解不等式 ll k=min((top-c)/d,(top-e)/f); c+=k*d; e+=k*f; printf("%lld %lld %lld %lld\n",c,d,e,f); } }else{ d=f=b/gcd; e=1; c=a/gcd+1; printf("%lld %lld %lld %lld\n",c,d,e,f); } } return 0; } void ex_gcd(ll a,ll b,ll& x,ll& y){ if(!b){ x=1; y=0; return; }else{ ex_gcd(b,a%b,x,y); ll temp=x; x=y; y=temp-a/b*y; } } vector<int> divide(int x){ vector<int>prime_factor; for(register int i=2;i*i<=x;i++){ if(x%i==0){ prime_factor.push_back(i); while(x%i==0) x/=i; } } if(x>1) prime_factor.push_back(x); return prime_factor; }