#UVa:11388-GCD LCM

灆洢 2016-04-28 10:17:41

基本上符合的答案就會是\(a = G, b = L\),原因如下:

先證明什麼時候會有解,由於\(G | a, b\)且\(a, b | L\),故至少\(G | a, b | L\),亦指在有解的情況下至少G要能整除L。

那在有解的情況下a如果要最小該會是多少呢?由於\(G | a\),故a為G的某個倍數,而其中最小的就為G。那在\(a = G\)的情況下一定會有解嗎?由於\(G \times L = a \times b\),而\(a = G\),所以\(G \times L = G \times b\),整理一下可得\(b = L\),所以在有解的情況下最符合的答案即是\((a, b) = (G, L)\)。

C++(0.000)

/*******************************************************/
/* UVa 11388 GCD LCM                                   */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/04/28                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int caseCount;
  while( scanf("%d", &caseCount) != EOF ){
    for( int caseNumber = 0 ; caseNumber < caseCount ; ++caseNumber ){
      int G, L;
      scanf("%d%d", &G, &L);

      if( L % G == 0 ){
        printf("%d %d\n", G, L);
      }
      else{
        printf("-1\n");
      }
    }
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料