题解：SP15965 ENIGMATH - PLAY WITH MATH

简单推一下这个式子！

$A \times x - B \times y = 0$；
移项得 $A \times x = B \times y$；
已知项为 $A,B$，我们把未知项移动到一边，则有：$\frac{x}{y} = \frac{B}{A}$。

欲求 $x,y$ 的最小正整数解，也就需要 $A,B$ 互质的时候，所以我们要对 $A,B$ 进行约分，约的数字即两者能同时除尽的数—最大公约数。于是就有了：

$\frac{x}{y} = \frac{B \div \gcd{(A,B)}}{A \div \gcd{(A,B)}}$

对于求最大公约数，用辗转相除法就可以了，在此不赘述。

所以最后，对于一组 $A,B$，就有最优解 $x = B \div \gcd{(A,B)},y = A \div \gcd{(A,B)}$。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <cstdio>
using namespace std;
int gcd (int x,int y)
{
    if (y == 0) return x;
    return gcd (y,x % y);
}
int main ()
{
    int t,a,b;
    cin>>t;
    while (t--)
    {
        cin>>a>>b;
        cout<<b / gcd (a,b)<<" "<<a / gcd (a,b)<<endl;
    } 
    return 0;
}