Akhilanand0011's blog

Gift Dilemma
By Akhilanand0011, history, 5 years ago, In English

can anyone help me to solve this problem https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=4628

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

The problem asks to count number of possible (x, y, z) such that Ax + By + Cz = P, where x, y, z >= 0. Also notice that C/gcd(A, B, C) ≥ 200.

If we iterate over all possible z, the problem simplifies to finding number of solutions for Ax + By = P - Cz, where minX = 0, maxX = (P - Cz) / B, minY = 0, maxY = (P - Cz) / A.

This is a linear diophantine equation. You can learn how to solve this here.

→ Reply