CEQU - Crucial Equation

Let us see the following equation,


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 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).


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 4 8
3 6 7

Case 1: Yes
Case 2: No

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

hide comments
imsaral: 2017-05-29 21:22:50

AC in one go :)
My 50th !! :D

jainsahil1997: 2017-05-23 07:19:29

Don't forget to add space between : and "yes" or "no"

shivamarya_123: 2017-04-29 15:16:02

there is only two cases case 1 and case 2 or more,and space between case and 1 or not.

shivamarya_123: 2017-04-29 15:13:27

i didn't understood input/output format.

namitp: 2017-04-11 18:41:20

very easy AC in one go...!

lonelybanboo: 2017-03-31 16:36:47

Gcd is enough.

stark_attack: 2017-02-18 19:33:57

space between : and Yes / No (*it cause me two WA)

code96maker: 2017-02-14 22:08:14

simple one for who knows diophantine equation...

ayushgupta1997: 2017-01-07 14:19:01

easy :) my 20th..got wa due to output format.Use Diophantine Equation...hope this helps:)

satya_jha123: 2016-12-02 15:43:08

Linear Diophantine Equations condition

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