牛客contest5668-F

传送门

题目大意

有t(t<1e5)次查询，每次查询给出两个数a,b(a,b<2e6)。输出一组满足下列要求的四个正整数cdef作为答案。若不存在满足条件的cdef，则输出”-1 -1 -1 -1″

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int	a, b, g, t;
ll c, d, e, f;	

int gcd( int a, int 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 res = exgcd( b, a % b, x, y );
	t = x;
	x = y;
	y = t - (a / b) * y;
	
	return res;
}

int main()
{
	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 ( int i = 2; i*i <= b; i++ )
			if ( b % i == 0 && gcd( i, b / i ) == 1 )
			{
				d = i;
				f = b / i;
				break;
			}
			
		if ( !d && !f )
		{
			puts("-1 -1 -1 -1");
			continue;
		}
		
		e = c = 0;
		int 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 );
	}
	
	return 0;
}