题目链接:http://lightoj.com/volume_showproblem.php?problem=1215
题意：已知三个数a b c 的最小公倍数是 L ,现在告诉你 a b L 求最小的 c ;
其实就是告诉你（最小公倍数LCM）LCM(x, y) = L 已知 x 和 L 求 最小的 y ;
L = LCM(x, y)=x*y/gcd(x, y);如果把x，y，L写成素因子之积的方式会很容易发现 L 就是 x 和 y 中素因子指数较大的那些数之积;
例如LCM(24, y) = 480，y最小为160
24 = 2^3 * 3 ;
480 = 2^5 * 3 * 5 ;
那么一个数的因子中一定含有 5 ，要最小，一定不含3，还有就是一定有2，因为是24*num/gcd(24, num),所以有2^5才能满足
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int oo = 0xfffffff;
const int N = ; LL gcd(LL a, LL b)
{
return b==?a:gcd(b, a%b);
} int main()
{
int T, t = ; scanf("%d", &T); while(T--)
{
LL a, b, L; scanf("%lld %lld %lld", &a, &b, &L); printf("Case %d: ", t++); LL x = a*b/gcd(a, b); if(L%x) puts("impossible");
else
{
LL y = L/x, r; /// x * y = L;逐步扩大 y，缩小 x; while(r = gcd(x, y), r!=)
{
x /= r;
y *= r;
}
printf("%lld\n", y);
}
}
return ;
}
/*
4 6 24
6 8 480
8
160
*/