UVA11388 GCD LCM(数论)

题目链接。

题意：

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

分析：

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

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

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

那么a*b=k₁*k₂*G^{^2}=L*G

这时一定有 a₁ = G, b₂ = k₁*k₂G 满足条件。即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 = 100+10;

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
";
               else cout << G << ' ' << L << endl;
        }
    }

    return 0;
}