ALiNew ALiNew

나머지

• [Algo Rhythm🕺💃] BOJ 4375 - 1

  Algo Rhythm🕺💃/BOJ 2021. 6. 23. 21:55

  문제 분석 1로만 이루어진 한 정수를 $x$, 2와 5로 나누어 떨어지지 않는 정수를 $n (1 \le n \le 10^5)$이라고 하자. 이 정수의 오른쪽 끝에 1을 붙이기 위해서는 정수의 자릿수를 한 자리 올린 후 1을 더하면 된다. 즉, $10 \times x + 1$을 하면 된다. 하지만 overflow가 발생할 수 있기 때문에 계속해서 오른쪽 끝에 1을 붙일 수 없다. 다행히도 문제에서 요구하는 것은 $x$ 자체가 아니라 $x \mod n == 0$을 만족할 때의 자릿수이다. 따라서, 중요한 것은 $x$가 아니라 $x \mod n$이라는 것을 알 수 있다. 그래서 정수의 오른쪽 끝에 1을 붙일 때 $x = 10 \times x + 1$이 아닌 $x = (10 \times x + 1) \mod n..

  Read More