문제 출처
backjoon 10430번 문제
0. 문제
ⅰ. 세 수 A, B, C가 주어졌을 때, 아래의 네 가지 값을 구하는 프로그램을 작성하시오.
■ (A+B)%C는 ((A%C)+(B%C))%C 와 같을까?
■ (A×B)%C는 ((A%C)×(B%C))%C 와 같을까?
■ 참고로 나머지 연산자는 일반적인 분배법칙이 성립되지 않는다.
■ (A+B)%C와 (A%C)+(B%C)는 같지 않고, (A×B)%C와 (A%C)×(B%C)는 같지 않다.
Ⅰ. 코드
#include <iostream>
using namespace std;
int main()
{
int a, b, c;
cin >> a >> b >> c;
printf("(%d + %d) %% %d = %d\n",a,b,c,(a+b)%c);
printf("((%d %% %d) + (%d %% %d)) %% %d = %d\n",a,c,b,c,c,((a%c)+(b%c))%c);
printf("(%d + %d) %% %d = %d\n",a%c, b%c, c, ((a%c)+(b%c))%c);
printf("(%d * %d) %% %d = %d\n",a,b,c,(a*b)%c);
printf("((%d %% %d) * (%d %% %d)) %% %d = %d\n",a,c,b,c,c,((a%c)*(b%c))%c);
printf("(%d * %d) %% %d = %d\n",a%c, b%c, c, ((a%c)*(b%c))%c);
return 0;
}■ 이 코드는 BOJ에서 정답처리 되지 않으니 주의
Ⅱ. 수식 증명
ⅰ. 나머지 연산의 일반적인 분배 법칙이 성립하지 않음 증명 (덧셈에 대해)
■ A = aC+m, B = bC+n으로 표현 가능. (a, b는 정수, 0≤m,n<|C|)
■ 1) (A+B)%C
= {(aC+m)+(bC+n)}%C // A와 B를 치환
= {(a+b)C+(m+n)}%C // 곱셈의 분배법칙에 따라 공통인수 C로 묶어줌
= (m+n)%C // 나머지 연산자의 성질에 따라 C로 묶인 값은 제거된다.
-> (m+n<|C|)라면 (m+n)%C = m+n이다.
(|C|≤m+n)라면 m+n = dC+l (d는 정수, 0≤l<|C|)로 표현 가능하며 (m+n)%C = (dc+l)%C = l이다
■ 2) (A%C)+(B%C)
= {(aC+m)%C}+{(bC+n)%C} // A와 B를 치환
= m+n // 나머지 연산의 성질에 따라 C로 묶인 값은 제거된다.
■ 즉, |C|≤m+n라면 (A+B)%C=l (0≤l<|C|)이고 (A%C)+(B%C)=m+n (|C|≤m+n)이므로 같지 않다.
ⅱ. (A+B)%C와 ((A%C)+(B%C))%C는 같음 증명
■ A = aC+m, B = bC+n으로 표현 가능. (a, b는 정수, 0≤m,n<|C|)
■ 1) (A+B)%C
= {(aC+m)+(bC+n)}%C // A와 B를 치환
= {(a+b)C+(m+n)}%C // 곱셈의 분배법칙에 따라 공통인수 C로 묶어줌
= (m+n)%C // 나머지 연산자의 성질에 따라 C로 묶인 값은 제거된다.
-> (m+n<|C|)라면 (m+n)%C = m+n이다.
(|C|≤m+n)라면 m+n = dC+l (d는 정수, 0≤l)로 표현 가능하며 (m+n)%C = (dc+l)%C = l
■ 2) {(A%C)+(B%C)}%C
= {(aC+m)%C}+{(bC+n)%C}%C // A와 B를 치환
= (m+n)%C // 나머지 연산의 성질에 따라 C로 묶인 값은 제거된다.
-> (m+n<|C|)라면 (m+n)%C = m+n이다.
(|C|≤m+n)라면 m+n = dC+l (d는 정수, 0≤l<|C|)로 표현 가능하며 (m+n)%C = (dc+l)%C = l이다.
■ 즉, 1)번식과 2)번식 모두 (m+n)%C로 같다.
ⅲ. (A-B)%C와 ((A%C)-(B%C))%C는 같음 증명
■ 위의 덧셈에 대한 증명과 거의 같으므로 접어두었다.
■ A = aC+m, B = bC+n으로 표현 가능. (a, b는 정수, 0≤m,n<|C|)
■ 1) (A-B)%C
= {(aC+m)-(bC+n)}%C // A와 B를 치환
= {(a-b)C+(m-n)}%C // 곱셈의 분배법칙에 따라 공통인수 C로 묶어줌
= (m-n)%C // 나머지 연산자의 성질에 따라 C로 묶인 값은 제거된다.
-> (m-n<|C|)라면 (m-n)%C = m-n이다.
(|C|≤m-n)라면 m-n = dC+l (d는 정수, 0≤l<|C|)로 표현 가능하며 (m-n)%C = (dc+l)%C = l이다.
■ 2) {(A%C)-(B%C)}%C
= {(aC+m)%C}-{(bC+n)%C}%C // A와 B를 치환
= (m-n)%C // 나머지 연산의 성질에 따라 C로 묶인 값은 제거된다.
-> (m-n<|C|)라면 (m-n)%C = m-n이다.
(|C|≤m-n)라면 m-n = dC+l (d는 정수, 0≤l<|C|)로 표현 가능하며 (m-n)%C = (dc+l)%C = l이다.
■ 즉, 1)번식과 2)번식 모두 (m-n)%C로 같다.
ⅳ. (A*B)%C와 ((A%C)*(B%C))%C는 같음 증명
■ 위의 덧셈에 대한 증명과 거의 같으므로 접어두었다.
■ A = aC+m, B = bC+n으로 표현 가능. (a, b는 정수, 0≤m,n<|C|)
■ 1) (A*B)%C
= {(aC+m)*(bC+n)}%C // A와 B를 치환
= (abC2+anC+bmC+mn)%C // 식을 풀어주었다.
= {(abC+an+bm)C+mn}%C // 곱셈의 분배법칙에 따라 공통인수인 C로 묶어줌.
= (mn)%C // 나머지 연산자의 성질에 따라 C로 묶인 값은 제거된다.
-> (mn<|C|)라면 (mn)%C = mn이다.
(|C|≤mn)라면 mn = dC+l (d는 정수, 0≤l<|C|)로 표현 가능하며 (m-n)%C = (dc+l)%C = l이다.
■ 2) {(A%C)*(B%C)}%C
= {(aC+m)%C}*{(bC+n)%C}%C // A와 B를 치환
= (mn)%C // 나머지 연산의 성질에 따라 C로 묶인 값은 제거된다.
-> (mn<|C|)라면 (mn)%C = mn이다.
(C≤mn)라면 mn = dC+l (d는 정수, 0≤l)로 표현 가능하며 (mn)%C = (dc+l)%C = l이다.
■ 즉, 1)번식과 2)번식 모두 (mn)%C로 같다.
ⅳ. (A/B)%C와 ((A%C)/(B%C))%C는 같을까?
■ 나누기에 대해서는 위와 같은 형태로 분배법칙이 성립하지 않는다.
■ 나누기에 대해서는 나눗셈을 곱셈의 형태로 바꾼 뒤, 곱셈에 대한 나머지 연산의 분배법칙을 적용해야한다.
■ 나눗셈을 곱셈의 형태로 바꾸는데는 페르마의 소정리 혹은 확장 유클리드 알고리즘이 사용된다.
■ 이에 대한 내용은 추후에 BOJ의 문제를 풀다보면 나올 것이므로 그 때 정리하려 한다.
■ 이를 이용한 나누기에 대한 나머지 연산의 분배법칙은 (A/B)%p = (A*Bp-2)%p = {(A%p)*(Bp-2)%p)}%p 이다.
Ⅲ. 결론
ⅰ. 나머지 연산에 대한 분배법칙 정리
■ 덧셈에 대한 법칙 : (A+B)%C = {(A%C)+(B%C)}%C
■ 뺼셈에 대한 법칙 : (A-B)%C = {(A%C)-(B%C)}%C
■ 곱셈에 대한 법칙 : (A*B)%C = {(A%C)*(B%C)}%C
■ 나누기에 대한 법칙 : (A/B)%C = {(A%p)*(Bp-2)%p)}%p