| Submit | All submissions | Best solutions | Back to list |
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 |
Case 1: Yes |
Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology
| Added by: | 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 |
hide comments
|
|||||||||||
|
2023-01-19 14:10:52
Be Careful with output form Last edit: 2023-01-19 14:11:33 |
|||||||||||
|
2022-07-09 03:48:51
Bézout's Lemma |
|||||||||||
|
2022-07-04 09:04:20
I submitted 4 times because the output format xD |
|||||||||||
|
2022-01-10 07:19:02
output format is this -> cout<<"Case "<<i<<": Yes"<<endl; cout<<"Case "<<i<<": No"<<endl; just copy paste it for better understanding :) |
|||||||||||
|
2021-10-23 16:07:13
got it if u didnt get it dont feel low..try your best and learn linear diaphantine eqution |
|||||||||||
|
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 |
|||||||||||
|
2021-10-11 13:03:57
Formatting the output was tougher than the actual problem -_- |
|||||||||||
|
2021-06-22 06:05:01
pay attention to the output format. |
|||||||||||
|
2021-06-07 06:30:31
Good question! only about the basic concept about linear diophantine, pretty simple |
|||||||||||
|
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. |
|||||||||||
RSS