백준 10430번

백준 10430번은 나머지 연산에 분배법칙(?)이 적용되는지 직접 코드를 짜서 확인하는 문제이다.

결론부터 이야기 하자면, 우리가 그 전에 알고 있었던 분배법칙은 성립하지 않지만, 특이한 방식에서는 분배법칙이 성립하는 것으로 보인다.

(A + B) % C = (A % C + B % C) % C가 성립한다는 것을 증명하기 위해,

A = CQ1 + r1
B = CQ2 + r2
로 둔 후에, 좌변의 식에 대입하면

(C * (Q1 + Q2) + r1 + r2) % C

가 된다.

나머지만을 연산하기 때문에, 좌변은

(R1 + R2) % C가 남고,

R1 + R2 = A % C + B % C가 된다.

그러므로 식이 성립한다는 것을 알 수 있다. 코드를 짤 때는 이런 복잡한 증명은 필요 없으므로, 주석은 생략한다.

#include <stdio.h>

int main(void) {
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	printf("%d\n", (a + b) % c);
	printf("%d\n", ((a % c) + (b % c)) % c);
	printf("%d\n", (a * b) % c);
	printf("%d\n", ((a % c) * (b % c)) % c);
	return 0;
}