首先对于C不能整除A的状况肯定排除
然后得到B=C/A
然后取G=GCD(A,B)
如果G==1,那么此时B就是解
否则的话，就证明A,B,的最小公倍数肯定不是C，因为其最小公倍数是A*B/G
那么我们就去掉这个公因子，方法是A/G,B*G
即可消去两者公共的倍数，同时还可以保证A*B是一个定值
循环直到G==1为止。。。是。。。是。。是。。。挺神奇的。。。
题意借鉴自https://blog.csdn.net/libin56842/article/details/46442083
https://blog.csdn.net/just_sort/article/details/50983350
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
typedef long long LL; int gcd(int a, int b)
{
return b==?a:gcd(b, a%b);
} int main()
{
int T;
cin>> T;
while(T--)
{
int a, b, c;
cin>> a >> c;
if(c % a != )
cout<< "NO SOLUTION" <<endl;
else
{
b = c / a;
if(gcd(a, b) == )
cout<< b <<endl;
else
{
while(gcd(a, b) != )
{
int temp = gcd(a, b);
a /= temp;
b *= temp;
}
cout<< b <<endl;
}
} } return ;
}