$Ax+By+Cz=P$ , $0\le x,y,z$ and $200 \le \frac{C}{gcd(A,B,C)}$.

For given $A,B,C,P$ find number of triplet $(x,y,z)$.

Solution:⌗

\begin{align} 200 &\le \frac{C}{gcd(A,B,C)} \newline C &\ge 200\times gcd(A,B,C) \newline \therefore C &\ge 200 \end{align}

Hence, we will rewrite the eqation as $Ax+By+Cz=P \Longrightarrow Ax+By=P-Cz=P'$

We will iterate over all possible values of $P'$(there will be maximum $\frac{10^{8}}{200}$), and for each value of $P'$ we will find number of pair $(x,y)$ that satisfy $Ax+By=P'$ , and sum them up.

We can use extended euclid to solve the diophantine equation and solve the modified problem. But in this post we will solve the problem in other way.

Popoviciu’s Theorem:⌗

[Don’t know the name of the theorem actually :p]

$ax+by=c$ and $0\le x,y$ . Find number of pair $(x,y)$ that satisfy the equation.

The answer is $\frac{c}{ab}-\{\frac{b’c}{a}\}-\{\frac{a’c}{b}\}+1$

  • $a\times a' \equiv 1 \text{ (mod $b$)}$

  • $b\times b' \equiv 1 \text{ (mod $a$)}$

  • $\{x\} = x-\lfloor x \rfloor$

Reference:⌗