Connection Status:
Competition Arena > FoxIntegerLevelOne

FoxIntegerLevelOne

SRM 535 · 2012-01-31 · by wrong

SRM 535 · 2012-01-31 · by wrong · Simple Math
Class Name: FoxAndGCDLCM
Return Type: long
Method Name: get
Arg Types: (long long, long long)
Problem Statement

Problem Statement

Fox Jiro and Eel Saburo are good friends. One day Saburo found two interesting positive integers: A and B.


On the next day, Saburo met Jiro and wanted to tell him the two integers. However, he managed to forget their values. All Saburo could remember was their greatest common divisor G and their least common multiple L.


You are given two longs: G and L. Find the original integers A and B, and return the value of A+B. If there are multiple pairs of A and B that correspond to G and L, pick the one that minimizes A+B. If it is impossible to find such A and B (i.e., Saburo made a mistake somewhere), return -1.

Notes

  • The greatest common divisor of two integers a and b is the largest positive integer that divides both a and b without any remainder.
  • The least common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b.

Constraints

  • G will be between 1 and 1,000,000,000,000 (10^12), inclusive.
  • L will be between 1 and 1,000,000,000,000 (10^12), inclusive.
Examples
0)
2
20
Returns: 14

The possible pairs of A and B are {2, 20} and {4, 10}. We need to pick {4, 10} since 4+10 is the smallest sum of A and B.

1)
5
8
Returns: -1

There are no pairs of A and B such that their greatest common divisor is 5 and their least common multiple is 8.

2)
1000
100
Returns: -1
3)
100
1000
Returns: 700
4)
10
950863963000
Returns: 6298430

Submissions are judged against all 227 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FoxAndGCDLCM with a public method long long get(long long G, long long L) · 227 test cases · 2 s / 256 MB per case

Submitting as anonymous