SRM373 Div2 250

問題

3つの正の整数X,Y,Pが与えられる。
2つの正の整数a,bについて、Pがa*X+b*Yの約数であるようなa+bが最小になるa+bを返す。

考え方

a,bでループを回し、その最小値を返す。
このとき、a,bはa*X+b*YがPで割り切れることを考えると、最大でもa==P&&b==PであればP*(X+Y)でPで割り切れるので、最大でもa,bはPまで回せばよいことがわかる。