Divisors and Reciprocals solution codechef- Alice is teaching Bob maths via a game called NN-guesser. Alice has a positive integer NN which Bob needs to guess. She gives him two pieces of information with which to do this: A positive integer XX, which denotes the sum of divisors of NN. Two positive integers AA and BB, which denote that the sum of reciprocals of divisors of NN is A/BA/B. Bob either needs to guess NN or tell that no such number exists. It can be shown that if a valid NN exists, it is unique.

Divisors and Reciprocals solution codechef

Alice is teaching Bob maths via a game called NN-guesser.

Alice has a positive integer NN which Bob needs to guess. She gives him two pieces of information with which to do this:

  • A positive integer XX, which denotes the sum of divisors of NN.
  • Two positive integers AA and BB, which denote that the sum of reciprocals of divisors of NN is A/BA/B.

Bob either needs to guess NN or tell that no such number exists.

It can be shown that if a valid NN exists, it is unique.

Input Format Divisors and Reciprocals solution codechef

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of a single line of input, containing three space-separated integers X,A,BX,A,B.

Output Format

For each test case, output a new line containing the answer — Alice’s number NN, or 1−1 if no such number exists.

Constraints Divisors and Reciprocals solution codechef

  • 1T10001≤T≤1000
  • 1X1091≤X≤109
  • 1A,B1091≤A,B≤109
  • gcd(A,B)=1gcd(A,B)=1

Sample Input 1 

2
4 4 3
4 1 1

Sample Output 1 

3
-1

Explanation Divisors and Reciprocals solution codechef

Test case 11: The divisors of 33 are 11 and 33. Their sum is 44 and the sum of their reciprocals is 4/34/3.

Test case 22: It can be proved that no positive integer NN exists whose divisors sum to 44 and reciprocals of divisors sum to 11.

Leave a Comment

Your email address will not be published.