$$z \equiv y \pmod x$$ 위 식을 만족하는 $a \le z \le b$를 찾는 문제입니다.
$a = px + r \left(0 \le r \lt \lvert x\rvert\right)$로 두면, 두 가지 경우로 나누어 볼 수 있습니다.
- $y \ge r$
- $px + y \le b$이면 $z = px + y$입니다.
- $px + \lvert x\rvert + y \le b$이면 답이 하나로 정해지지 않습니다.
- $y \lt r$
- $px + \lvert x\rvert + y \le b$이면 $z = p + \lvert x\rvert + y$입니다.
- $px + 2\lvert x\rvert + y \le b$이면 답이 하나로 정해지지 않습니다.
참고
- 입력에서는 $a > b$일 수도 있습니다.
- 답이 하나가 아닌 경우의 출력은
Unknwon
이지Unknown
이 아닙니다. - Rust에서는
div_euclid
,rem_euclid
메서드를 이용하면 나머지가 양수가 되도록 할 수 있습니다.
코드
fn solve(li: i64, ri: i64, div: i64, rem: i64) -> Option<i64> {
let div_abs = div.abs();
if !(0..div_abs).contains(&rem) {
return None
}
let rem = rem.rem_euclid(div);
let li_quot = li.div_euclid(div);
let li_rem = li.rem_euclid(div);
let mut mult_part = li_quot * div;
if rem < li_rem {
mult_part = mult_part + div_abs;
}
if mult_part + div_abs + rem <= ri {
None
} else if mult_part + rem <= ri {
Some(mult_part + rem)
} else {
None
}
}