Diophantine equation

           https://en.wikipedia.org/wiki/Diophantine_equation

            Diophantine equation is ax + by = c
give an integer solution only if gcd(a,b) divides c.

down vote

Solving Linear Diophantine equations ax + by = c and gcd(a, b) divides c. Divide a, b and c by gcd(a,b). Now gcd(a,b) == 1 Find solution to aU + bV = 1 using Extended Euclidean algorithm Multiply equation by c. Now you have a(Uc) + b (Vc) = c You found solution x = U*c and y = V * c problem realted :https://www.codechef.com/APRIL12/problems/DUMPLING/ EXPLANATION Given two integers A and B, let us try to figure out all the reachable integers. Consider jumping X units to the right as adding X and jumping X units to the left as subtracting X. Working out an example always helps. If A = 4 and B = 6, observe that we can only reach every integer in  the set { ..., -8, -6, -4, -2, 0, 2, 4, 6, 8, ... } If A = 3 and B = 5, observe that we can only reach every integer in  the set { ..., -3, -2, -1, 0, 1, 2, 3, ... } If you try out other simple examples, soon you will be able to notice that given A and B, one can only reach integers that are multiples of the greatest common divisor (gcd) of A and B.  Another way of looking at this is that every integer P that satisfies, Ax + By = P, is reachable.  Here x and y are arbitrary integers. [ x=2 means that the chef jumps 2A units to the right, x=-5 means he jumps 5A units to the left]. It can be proved that P is a multiple of the gcd of A and B. Thus, Chef Shifu can reach multiples of the gcd of A and B. Let X = gcd(A,B). Chef Po can reach multiples of the gcd of C and D. Let Y = gcd(C,D). Thus, every multiple of X which is also  a multiple of Y can always be reached by both the chefs. If we find the least common multiple of X and Y, say L, then every multiple of L can be reached by both. Know more about Greatest Common Divisor and Least Common Multiple. Coming back to the solution - count all the positive reachable integers in the interval (0,K].  This is simply K/L. The number of negative reachable integers must be same due to symmetry.  And don't forget to add the center point too. So the answer is 2 * (K/L) + 1. Here, the only problem was that L may not fit into a 64-bit integer but the final answer would always fit  into a 64-bit signed integer. This could be handled by a simple repeated division. From the definition of the least common multiple, we have L = (X * Y)/gcd(X,Y) , this is same  as, S = X/gcd(X,Y) , L = S*Y T = K/L = K/(S * Y), this is same as, R = K/S , T = R/Y Thus, all the intermediate results could fit into 64-bit integers. Or you could learn to use your  favorite library that handles large integers :) ANSWER: #include<iostream> #include<cstdio> #include<cassert> #define SI(x) scanf("%d",&x) typedef long long LL; using namespace std; #define MXT 50000 LL a,b,c,d; LL ans,k; int t; LL gcd(LL a,LL b) {     if(b==0) return a;     return gcd(b,a%b); } LL lcm(LL a,LL b) {     LL ret = 1ll*a*b;     LL g = gcd(a,b);     ret/=(1ll*g);     return ret; } int main() {     SI(t);     while(t-- >0)     {         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);         scanf("%lld",&k);         LL g1 = gcd(a,b);         LL g2 = gcd(c,d);         LL g = gcd(g1,g2);                  g1/=g;         ans = (k/g1);         ans = ans/g2;         ans = 2ll*ans + 1;                  printf("%lld\n",ans);     }     return 0;   }