好吧，被大白书上的入门题给卡了。=_=||

已知LCM(A, B) = C，已知A和C，求最小的B

一开始我想当然地以为B = C / A，后来发现这时候的B不一定满足gcd(A, B) = 1

A要不断地除去gcd(A, B)，直到满足gcd(A, B) = 1

B最后就应该乘上A除去的值

1 #include 
      
        2  3 typedef long long LL; 4  5 LL gcd(LL a, LL b) 6 { return b == 0 ? a : gcd(b, a%b); } 7  8 int main() 9 {10     int T;11     scanf("%lld", &T);12     LL a, c;13     while(T--)14     {15         scanf("%lld%lld", &a, &c);16         if(c % a == 0)17         {18             LL b = c / a;19             LL g = gcd(a, b);20             LL t = 1;21             while(g != 1)22             {23                 a /= g;24                 t *= g;25                 g = gcd(a, b);26             }27             printf("%lld\n", b*t);28         }29         else puts("NO SOLUTION");30     }31 32     return 0;33 }