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
rithwhick_2003: 2021-10-23 16:07:13

got it if u didnt get it dont feel low..try your best and learn linear diaphantine eqution

rithwhick_2003: 2021-10-23 16:04:36

some one help..at a very brute force i could think of..let c2=b%a,c1=c%a....and i would run a loop of i=0 to a-1;
so that (c2*i)%a ==c1 and c2*i<=c1 ...i could only think of this..and obviously constraints breaks at certain time due to 1e6 of a ....so i need a better optimization or any other method to solve this

rimuru_404: 2021-10-11 13:03:57

Formatting the output was tougher than the actual problem -_-

sureshmangs: 2021-08-15 10:48:17

It's Yes not YES. LOL

sankalp_7: 2021-06-24 09:17:07

Last edit: 2021-07-09 05:23:39
itsabi_z1: 2021-06-22 06:05:01

pay attention to the output format.

anchord: 2021-06-07 06:30:31

Good question! only about the basic concept about linear diophantine, pretty simple

messier22: 2021-05-08 13:35:46

I'm a faggot.

Last edit: 2021-05-08 22:53:03
crawler_123: 2021-04-23 20:01:27

The Problem is based on finding solution for Linear Diophantine Equation, hope this hint will help any one of you.

sk128: 2021-04-05 15:34:14

Got AC ?

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