Monday, August 3, 2015

UVa 11388 - GCD LCM

Problem

Problem Link - UVa 11388 - GCD LCM

Given two positive integers $(G, L)$, we have to find a pair of integers $(a,b)$ such that $gcd(a, b)=G$ and $\text{lcm}(a, b)=L$. If there are multiple such pairs, we have to find the pair where $a$ is minimum. Also, both $a$ and $b$ needs to be positive.

Solution

We don't know the value of $(a,b)$ yet. Here is how I approached the problem.

Value of $a$

What we know that $gcd(a,b) = G$. So, $G$ divides $a$ and $b$. Therefore, $a$ is a multiple of $G$. We also need to make sure that $a$ is as small as possible. So, what is the smallest positive number that can be divided by $G$? The answer is $G$ itself.
$$\therefore a = G$$

Existence of Solution

Next, we know that $lcm(a,b)$ is the smallest positive number which is divisible by both $a$ and $b$. Since $a=G$ and $a \: | \: lcm(a,b)$, it follows that $a = G$ should divide $lcm(a,b) = L$. If $L$ is not divisible by $G$, then no solution exists. 
$$\therefore \text{if } (G \not| L), \text{no solution exists}$$

Value of $b$

The value of $b$ can be derived in the following way. We know that:

$gcd(a,b) \times lcm(a,b) = a \times b$
$G \times L = G \times b$
$b = \frac{G\times L}{G}$
$\therefore b = L$.

Summary 

  1. $a = G$
  2. If $G \not| L$, no solution exists
  3. $b = L$
  4. $\therefore (a,b) = (G,L)$

Code

Here is the code in C++
#include <bits/stdc++.h>

int main () {
    int kase;
    scanf ( "%d", &kase ); //Input number of case

    while ( kase-- ) {
        int G, L;
        scanf ( "%d %d", &G, &L ); //Take input

        int a, b; //Need to find their value
        
        a = G;
        
        if ( L % G != 0 ) {
            printf ( "-1\n" ); //No Solution
            continue;
        }
        
        b = L;
        
        printf ( "%d %d\n", a, b );
    }

    return 0;
}

No comments:

Post a Comment

Leave comments for Queries, Bugs and Hugs.