쿨한 물건 구매

summary:

$D,P,Q \leq 10^9$ 가 주어지고,

$D \leq Pa + Qb (0 \leq a,b)$인 수 $Pa+Qb$의 최솟값을 찾는 문제이다.

solution:

P의 배수(=$Pa$)를 고정시키면 Pa+Qb의 최솟값을 구할 수 있다. 그 중에서 가장 작은 값이 정답이 된다.

그렇지만 D보다 작거나 같은 P의 배수 n/p개를 전부 확인할수 없다.

고려해야 할 P의 배수의 범위를 생각해볼 때 $Pa$가 $PQ$를 넘으면, $P(Q+x)$처럼 되면 Q의 배수로도 PQ를 만들 수 있으므로 $Px$와 같은 경우가 된다.

그러므로 P의 배수 중 D를 넘지 않는 선에서, $PQ$이하까지만 보면 된다.

P>Q일때, min(D/P,Q)<=min(D/P,P)<=sqrt(D)이므로 시간 복잡도는 sqrt(D)가 된다.