CEQU - Crucial Equation Spoj Problem Solution & Logic

http://www.spoj.com/problems/CEQU/

মজার একটি প্রোবলেম , একটি ইকুয়েশন ax + by = c  এর কো-এফিসিয়েন্ট গুলো (  a,b,c ) দেয়া থাকবে ।

 তোমায় , বলতে হবে --- equation টি'র আদৌ কোনো সলিউশন আছে ?? নাকি , নাই ????
এখন , ধরো  a=8 , b=4 & c=3 দেয়া আছে , তোমায় বলা হলোও - এই ইকুয়েশন এর কোনো সলিউশন আছে কি না ??তাহলে চলো, চেক করি --------------------------

                                       8x + 4y = 3
                                      

                                      যদি , x=1 & y= -1        8 - 4 = 4
                                      যদি,   x=2 & y=-2        16-8=8 
                                        যদি, x=3 & y= - 2       24-8=16
                                       যদি,  x=4 & y= -2        32-8=24 
                                          যদি, x=5 & y=-9        40-36=4
                                   ..................................................................................
                                   ....................................................................................

এভাবে সারাজীবন চেষ্টা করলেও , উত্তর কোনোদিনও ৩ হবে না , এর মানে এর কোনো সলিউশন নেই ।
বলো তো , কিভাবে ? আমি এত্ত সিউর হচ্ছি --- যে , এর কোনো সলিউশন নেই ??

তুমি কি লক্ষ করেছো ???  ইকুয়েশন এর উত্তর 4,8,16,24,4 ............ ইত্যাদি হয় ।শুধু তাই নয় , এই উত্তর গুলো , সবসময়ই  a & b  এর   গ সা গু এর গুণিতক  হবে । অর্থাৎ , c এর মান যদি a & b এর গ সা গু এর গুণিতক হয় , তাহলেই কেবল এর সলিউশন সম্ভব , আর না হলে নয় ।

চলো , এবার কোড দেখি

#include <iostream>

using namespace std;

long int gcd(long long int a , long long int b){
   
    if(b==0 || a==0) {
        return 0;
    }
    if(b%a==0){
        return a;
    }
    else{
        return gcd(b%a,a);
    }
       
}

int main()
{
    long long int T,a,b,c,g;
   
    cin>>T;
   
    for (int i = 1; i <= T; ++i)
    {
       
        cin>>a>>b>>c;
       
        g=gcd(a,b);
       
        if(c%g==0)
            cout<<"Case "<<i<<": Yes"<<endl;
        else
            cout<<"Case "<<i<<": No"<<endl;
    }
    return 0;
}