【LightOJ】1215 - Finding LCM（数论）

题目链接：这里写链接内容

1215 - Finding LCM PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM (a, b, c) = L if and only if L is the least integer which is divisible by a, b and c.

You will be given a, b and L. You have to find c such that LCM (a, b, c) = L. If there are several solutions, print the one where c is as small as possible. If there is no solution, report so.

Input Input starts with an integer T (≤ 325), denoting the number of test cases.

Each case starts with a line containing three integers a b L (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012).

Output For each case, print the case number and the minimum possible value of c. If no solution is found, print ‘impossible’.

Sample Input 3 3 5 30 209475 6992 77086800 2 6 10

Output for Sample Input Case 1: 2 Case 2: 1 Case 3: impossible

我们肯定是要先求k = LCM（a，b） ，然后判断 l % k ， 如果不能整除，肯定是不满足的。如果可以整除，那么我们得到了 k 中不属于 l 的素因子。但是为了使 k / GCD（ans，k）* ans == l ，我们需要找出 k 和 ans 的公共素因子，并且让 ans 乘以其指数的差，这样才能保证 k / GCD（ans，k）不会把 k 中“有用的”质因子除掉。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
LL GCD(LL a,LL b)
{
    return b == 0 ? a : GCD(b,a%b);
}
LL LCM(LL a,LL b)
{
    return a / GCD(a,b) * b;
}
int main()
{
    int T;
    LL a,b,l;
    int Case = 1;
    cin >> T;
    while (T--)
    {
        cin >> a >> b >> l;
        printf ("Case %d: ",Case++);
        LL k = LCM(a,b);
        if (l % k != 0)
            puts("impossible");
        else
        {
            LL ans = l / k;
            while (1)
            {
                LL g = GCD(k,ans);
                if (g == 1)
                    break;
                ans *= g;
                k /= g;
            }
            cout << ans << endl;
        }
    }
    return 0;
}