Monk and Fredo number of + ve x ,y sush that a*x+b*y=d

Monk and Fredo

Fredo and you are talking about a movie that you have recently watched while Monk is busy teaching Number Theory. Sadly, Monk caught Fredo talking to you and asked him to answer his question in order to save himself from punishment. The question says:
Given two weights of $a$ and $b$ units, in how many different ways you can achieve a weight of $d$ units using only the given weights? Any of the given weights can be used any number of times (including $0$ number of times).
Since Fredo is not able to answer the question, he asked you to help him otherwise he will get punished.
Note: Two ways are considered different if either the number of times $a$ is used or number of times $b$ is used is different in the two ways.
Input Format:
The first line of input consists of an integer $T$ denoting the number of test cases.
Each test case consists of only one line containing three space separated integers $a$, $b$ and $d$.
Output Format:
For each test case, print the answer in a separate line.
Constraints:
$1\le T\le {10}^5$
$1\le a<b\le {10}^9$
$0\le d\le {10}^9$

SAMPLE INPUT

 

4
2 3 7
4 10 6
6 14 0
2 3 6

SAMPLE OUTPUT

 

1
0
1
2

Explanation

Test case $1$:
$7$ can only be achived by using $2$ two times and $3$ one time.
Test case $2$:
$6$ can't be achieved by using $4$ and $10$. So, $0$ ways are there.
Test case $3$:
$0$ can be achieved by using $0$ times $6$ and $0$ times $14$. So, there is only one way,
Test case $4$:
$6$ can be achieved by using $2$ three times or $3$ two times. So, there are two different ways of getting $6$.

Brief Description: Given $a$, $b$ and $d$, find the number of pairs $(x,y)$ such that $0\le x,y$ and $a\ast x+b\ast y=d$.
Prerequisite: Euclid Extended Algorithm
Difficulty: Medium
Detailed Explanation:
As we know that $a\ast x+b\ast y=d$ is a linear Diophantine equation in two variables. The solution of this equation exists if and only if $d$ is divisible by the $GCD(a,b)$.
Solution 1:
The simplest solution is to try all the values of $x$ and $y$. As we know that the values of $x$ will be in range from $[0,\frac{d}{a}]$. Similarly the values of $y$ will be in the range $[0,\frac{d}{b}]$. Time complexity of this solution is $O\left(\frac{d^2}{a\ast b}\right)$ which won't run within the time limit.
Solution 2:
$a\ast x+b\ast y=d$
$a\ast x=d-b\ast y$
We know that for one value of $y$ there is at-most one $x$ which will satisfy this equation. So, iterate over all values of $y$ in the range $[0,\frac{d}{b}]$ and check if $(d-b\ast y)$ is divisible by $a$ or not. Time complexity of this solution is $O\left(\frac{d}{b}\right)$ which is better than previous solution's complexity but still not good enough to pass within the time limit.
Note: We can also iterate over all values of $x$ from $[0,\frac{d}{a}]$ and check if $(d-a\ast x)$ is divisible by $b$ or not. But $a<b$, so $\frac{d}{b}<\frac{d}{a}$.
Solution 3:
Let $y1$ be the smallest non negative number such that $(d-b\ast y1)$ is divisible by $a$. We can say that $y1$ is the first value of $y$ such that $(d-b\ast y)$ is divisible by $a$.
If we have $y1$, the next value of $y$ will be $y1+a$.
Why ??
Let $y=y1+a$.
$d-b\ast y=d-b\ast (y1+a)=d-b\ast y1-b\ast a$
But we know that $d-b\ast y1$ is divisible by $a$ and $b\ast a$ is also divisible by $a$, so $d-b\ast (y1+a)$ will also be divisible by $a$.
So, the values of $y$ will be $y1,y1+a,y1+2\ast a,y1+3\ast a,...,y1+n\ast a$ where $y1+n\ast a\le \frac{d}{b}$.
The values of $y$ seems to be a Arithmetic Progression. So we can easily calculate number of terms in the Arithmetic progression using $y1+n\ast a\le \frac{d}{b}$ equation.
$n=\frac{\frac{d}{b}-y1}{a}$
So number of terms in the Arithmetic progression is equal to $n+1$.
Now the only part thats left is to find the value of $y1$. An obvious solution is to iterate over all values of $y$ and break as soon as we find the first value such that $d-b\ast y$ is divisible by $a$. Time complexity of this solution is $O\left(\frac{d}{b}\right)$ in worst case. But this solution is faster then previous solutions in other cases.
Exercise: What is the worst case for this solution ?
Solution 4:
Note: A small optimization is divide both the side of the equation $a\ast x+b\ast y=d$ by the $GCD(a,b)$. Why ?? Think about it.
We can compute the first value of $y1$ using Modulo Inverse (Extended Euclid).
$a\ast x+b\ast y=d$
$y=\frac{d-a\ast x}{b}$
Taking modulo $a$ both side.
$y1=y\%a=\frac{d-a\ast x}{b}\%a=\frac{d}{b}\%a$
Now we need to check if $(d-b\ast y1)$ is divisible by $a$.
Let $z=(d-b\ast y1)$
$z\%a=(d-b\ast y1)\%a$
$z\%a=(d\%a-(b\%a)\ast (\frac{d}{b}\%a\left)\right)$
$z\%a=0$
So $y1$ is the first value of $y$ such that $(d-b\ast y)$ is divisible by $a$.
We can compute $y1$ in $O\left(log\right(max(a,b))$ and number of term using the formula computed in the previous solution ($n=\frac{\frac{d}{b}-y1}{a}$ ) in $O\left(1\right)$.
So the overall time complexity is $O\left(log\right(max(a,b)\left)\right)$.
Time Complexity: $O\left(log\right(max(a,b)\left)\right)$
Space Complexity: $O\left(1\right)$

#include<bits/stdc++.h>
#define dd double
#define ll long long
using namespace std;
ll g, x, y;
void extendedEuclid(ll A,ll B) {
    if(B == 0) {
        g = A;
        x = 1;
        y = 0;
    }
    else {
        extendedEuclid(B, A%B);
        ll temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}
int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        ll a,b,d,e=0;
        cin>>a>>b>>d;
        extendedEuclid(a,b);
  if(d%g !=0){cout<<"0\n";continue;}
        ll k1=ceil(dd(-x)*(dd(d)/dd(b))),k2=floor((dd)y*((dd)d/(dd)a));
  if(k1<=k2)
   cout<<k2-k1+1<<"\n";
  else
   cout<<"0\n";
    }
    return 0;
}