Benefit UVA

首先对于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 = 10010, INF = 0x7fffffff;
typedef long long LL;

int gcd(int a, int b)
{
    return b==0?a:gcd(b, a%b);
}


int main()
{
    int T;
    cin>> T;
    while(T--)
    {
        int a, b, c;
        cin>> a >> c;
        if(c % a != 0)
            cout<< "NO SOLUTION" <<endl;
        else
        {
            b = c / a;
            if(gcd(a, b) == 1)
                cout<< b <<endl;
            else
            {
                while(gcd(a, b) != 1)
                {
                    int temp = gcd(a, b);
                    a /= temp;
                    b *= temp;
                }
                cout<< b <<endl;
            }
        }

    }

    return 0;
}