2020牛客暑期多校训练营（第三场）F

题目描述

  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;
}