UVA11388 GCD LCM(数论)

题目链接。

题意：

给定两个数，一个G，一个L，找出两个数a,b(a<=b)，使得这两个数的最大公约数为G，最小公倍数为L,且（a最小)。

分析：

当a，b存在时，a一定为G。

自己证了一下，数学方面不太擅长。

假设 a 最小为 kG (其中 k1 != 1), b为 kG, 即 a = G，不满足条件。

那么a*b=k*k*G=L*G

这时一定有 a = G, b = k*kG 满足条件。即a不符合题意。

设 a = G, b = kG

因为 L*G = a*b

b = L*G/a = L.

因为b = kG

b/a=kG/G=k

所以要满足的条件为 L % G == 0

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = +;

typedef long long LL;

int main() {

  //  freopen("my.txt", "r", stdin);

    int T;

    LL G, L;

    scanf("%d", &T);

    while(T--) {

        while(cin >> G >> L) {

               if(L % G) cout << "-1\n";

               else cout << G << ' ' << L << endl;

        }

    }

    return ;

}

KG

UVA11388 GCD LCM(数论)