Gift Dilemma - UVA 12775

$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.
Read more →

Fraction and Sequence - UVA 13041

How many triplet $(a,b,c)$ are there such that $0\le a,b,c \le L$ and $\sum_{x=0}^{\infty}{(ax^{2}+bx+c)\times (\frac{1}{10})^{x+1}} = \frac{p}{q}$ , for given $p,q,L$. Inside Math: Suppose, $A = \sum_{x=0}^{\infty}{ax^2\times (\frac{1}{10})^{x+1}}$ $B = \sum_{x=0}^{\infty}{bx\times (\frac{1}{10})^{x+1}}$ $C = \sum_{x=0}^{\infty}{c\times (\frac{1}{10})^{x+1}}$ Hence, $\sum_{x=0}^{\infty}{(ax^{2}+bx+c)\times (\frac{1}{10})^{x+1}} = A+B+C$ Now, we know(Actually we don’t know this, we have to prove this. We’ll try to prove this in some other section) that: $\sum_{x=0}^{\infty}{x^{2}r^{x+1}} = \frac{r^{2}(r+1)}{(r-1)^{3}} \tag{1}$ $\sum_{x=0}^{\infty}{xr^{x+1}} = \frac{r^{2}}{(r-1)^{2}} \tag{2}$
Read more →