【题目】点击打开链接

【解题思路】本题要求寻找最小的B，使得lcm(A,B)=C。这里容易想当然地认为B=C/A就是答案。实际上是错误的做法。因为lcm(A,C/A)不一定等于C，如果想让lcm(A,C/A)==C，必须有gcd(A,C/A)==1。通过恒等式a*b==gcd(a,b)*lcm(a,b)即可证明。这就提示我们得到临时的B之后，要想办法将A,B变为互素的两个数。还是利用恒等式，我们可以事先求出d=gcd(A,B)，只需要B*=d，同时将A/=d。即可消去两者公共的倍数，同时还可以保证A*B是一个定值。不过这里又要注意了：不可以只消去一次就以为gcd(A,B)=1了，要一直反复多次尝试，直到gcd(A,B)==1为止。

【AC代码】

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int tt,a,b,c;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&a,&c);
        if(c%a!=0)
        {
            puts("NO SOLUTION");
        }
        else
        {
            b=c/a;
            int d=gcd(a,b);
            while(d!=1)
            {
                b*=d;
                a/=d;
                d = gcd(a,b);
            }
            printf("%d\n",b);
        }
    }
    return 0;
}