1215 Finding LCM

题意：

$L=LCM(a, b,c)$ ，输入$a \quad b\quad L$，求满足条件的最小$c$。

输入：

$T$组测试样例。

3
3 5 30
209475 6992 77056500
2 6 10

输出：

Case 1: 2
Case 2: 1
Case 3: impossible

思路：

前置1：

首先，对于$L=lcm(a, b,c)$。可以进行一个等价代换：
$$lcm(a, b, c) = lcm(lcm(a, b), c)$$
记$lcm(a, b) = t$，则$L = lcm(t, c)$

此时 $L, t$都已知。且$lcm(t, c) = t * c / gcd(t, c) = L$

前置2：

由唯一分解定理可知：
$$t = p_1^{a_1} * p_2^{a_2} * \cdot\cdot\cdot p_n^{a_n}$$

$$c = p_1^{b_1} * p_2^{b_2} * \cdot\cdot\cdot p_n^{b_n}$$

$$L =lcm(t, c) = p_1^{max(a_1, b_1)} * p_2^{max(a_2,b_2)} * \cdot\cdot\cdot * p_n^{max(a_n, b_n)}$$

综述：

由前置2可以得到 若$c$使得$lcm(t,c) =L$ ，则$L$一定可以整除$t$，否则c便不满足条件。

记：
$$x = \frac{L}{t}$$
这里用实际例子解释比较容易理解一点： $a=3, b=5, L=90$

此时 $t = 15, x = 6$
$$L = 2 * 3^2 * 5$$
$$t = 3 * 5$$
肉眼可见的此时$c$应该是$2 * 3^2$ 才可以满足$lcm(t, c) = L$(前置2)

而 $x = \frac{L}{t} = 2 * 3$，此时我们可以发现 $x$距我们要找的$c$差一个3。

相当于$L$中有$p$个3， t中有$q$个3.而$x$中有$p - q$个3 ，我们便对 $t$和$x$求q次最大公约数。

每次对t除3，对x成3。 最终x中3的次数为$p$,也就是$L$中3的次数。 当$gcd(t,x)=1$的时候，x便为我们要求的$c$

代码：

#include <cstdio>

typedef long long LL;
using namespace std;
LL a, b, L;

LL gcd(LL a, LL b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}
LL lcm(LL a, LL b){
    return a / gcd(a, b) * b;
}

int main(){
    int T;
    scanf("%d", &T);

    for(long long Case = 1; Case <= T; ++ Case){
        printf("Case %lld: ", Case);
        scanf("%lld %lld %lld", &a, &b, &L);
        LL t = lcm(a, b);
        if(L % t){
            puts("impossible");
        }
        else{
            LL res = L / t;
            while(1){
                LL d = gcd(res, t);
                if(d == 1){
                    break;
                }
                res *= d;
                t /= d;
            }
            printf("%lld\n", res);
        }
    }
    return 0;
}