LightOj 1215 - Finding LCM（求LCM(x, y)=L中的 y ）

题目链接: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

*/

巴特西

LightOj 1215 - Finding LCM（求LCM(x, y)=L中的 y ）

最新文章

热门文章