14장에서 소개했던 나머지 연산의 분배 법칙을 기억하신다면, 3번 조건을 만족하는 수를 하나하나 만들면서 그 중 2번 조건을 만족하는 수를 걸러내기란 어렵지 않음을 아실 겁니다. c를 앞에서부터 한자리씩 만들어갈 때, 지금까지 만든 c의 뒤에 숫자 x를 붙인 결과인 c * 10 + x를 n으로 나눈 나머지는 실제 c를 모르더라도 알 수 있습니다. 다음과 같은 성질이 성립하기 때문입니다.
```
((c mod n) * 10 + x) mod n = (c * 10 + x) mod n
```
따라서 한 자리 씩 c를 만들어 갈 때 중요한 것은 현재 숫자가 아니라 c를 n으로 나눈 나머지가 됩니다. 이 점을 이용하면 n으로 나눈 나머지가 m인 최소 숫자를 쉽게 찾을 수 있습니다.
...
위 설명인데요, c를 몰라도 알 수 있다는 것이 이해가 안 됩니다. 설명해주실 수 있는 분 계신가요? 미리 감사드립니다. (14장의 모듈라 연산 관련된 부분은 읽었습니다)
cadenzah 4년 전
29.5번 어린이날 문제 풀이에 보면 이런 내용이 있습니다.
...
14장에서 소개했던 나머지 연산의 분배 법칙을 기억하신다면, 3번 조건을 만족하는 수를 하나하나 만들면서 그 중 2번 조건을 만족하는 수를 걸러내기란 어렵지 않음을 아실 겁니다. c를 앞에서부터 한자리씩 만들어갈 때, 지금까지 만든 c의 뒤에 숫자 x를 붙인 결과인 c * 10 + x를 n으로 나눈 나머지는 실제 c를 모르더라도 알 수 있습니다. 다음과 같은 성질이 성립하기 때문입니다.
```
((c mod n) * 10 + x) mod n = (c * 10 + x) mod n
```
따라서 한 자리 씩 c를 만들어 갈 때 중요한 것은 현재 숫자가 아니라 c를 n으로 나눈 나머지가 됩니다. 이 점을 이용하면 n으로 나눈 나머지가 m인 최소 숫자를 쉽게 찾을 수 있습니다.
...
위 설명인데요, c를 몰라도 알 수 있다는 것이 이해가 안 됩니다. 설명해주실 수 있는 분 계신가요? 미리 감사드립니다. (14장의 모듈라 연산 관련된 부분은 읽었습니다)