CEQU - Crucial Equation


Let us see the following equation,

                                            ax+by=c

Given three positive integers a, b and c. You have to determine whether there exists at least one solution for some integers value of x and y where x, y may be negative or non-negative integers.

For example if a=2, b=4 and c=8 then the equation will be 2x+4y=8, and hence, for x=2 and y=1, there exists a solution.

Let us see another example for a=3, b=6 and c=7, so the equation will become 3x+6y=7 and there exists no solution satisfying this equation.

Input

Input starts with an integer T (1<=T<=105) denoting the number of test cases. Each test case contains three integers a, b, and c. (1<=a, b, c<=106).

Output

For each test case of input print the case number and “Yes” if there exists at least one solution, print “No” otherwise.

Sample Input

Output for Sample Input

2
2 4 8
3 6 7

Case 1: Yes
Case 2: No

Problem Setter: Md Abdul Alim, CEO and Founder at CodeMask


hide comments
amit_dubey99: 2020-06-16 19:04:34

those Case 1 2 stuff sucks, cost me WA, but m happy finally it got AC :)

priyankarai: 2020-06-09 16:21:31

very bad problem, got WA just because wrong display of output,no focus on concept but only focussing on visuals

rky673: 2020-05-26 18:46:29

Printing the output is difficult compared to the question itself. Cost me a WA as I printed yes/no in uppercase :p

hemantsood: 2020-05-21 09:16:07

Hey print "Case 1" too otherwise you get wrong answer

iamprinceraj: 2020-05-16 06:56:43

Problem is easy, but we need to format the output as the 1st output shows "Case 1: Yes", 2nd output shows "Case 2: No" similarly 3rd output will show "Case 3: Yes/No" and so on ..

Last edit: 2020-05-16 06:57:45
abu_rifat: 2020-05-01 13:28:13

Find GCD(A,B), If(C%GCD) No. Else Yes.

aman005mishra: 2020-04-24 22:47:25

Use this format otherwise you will unnecessarily waste time thinking that there is some logical error
cout<<"Case "<<i<<":"<<" Yes/No"<<"\n";

Last edit: 2020-04-24 22:48:51
pratyushmj1: 2020-04-14 17:00:57

The output format is different follow the sample :).
You also need to update the case
Ex Case i: ans.

Last edit: 2020-04-14 17:04:41
rsinght111: 2020-01-29 12:45:35

showing output is more difficult than to slove the qstn

koulick424: 2020-01-16 17:25:32

Diophantine equation-hint


Added by:Md Abdul Alim
Date:2014-10-15
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem