[BOJ] 3944 나머지 계산

문제 링크

 

https://www.acmicpc.net/problem/3944

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

이 문제는 입력받은 모든 자릿수를 더하고, 이를 b-1로 나눈 나머지를 구하면 답을 구할 수 있다. 자세한 식 도출 과정은 다음과 같다.

 

 

123456(7) mod 6을 예로 들어보자.

123456(7)을 10진수로 변환하면

 

1 * 7^5 + 2 * 7^4 + 3 * 7^3 + 4 * 7^2 + 5 * 7^1 + 6 * 7^0

 

이다. 이 수에 mod 6을 하면 모듈러 연산의 분배법칙을 이용하여

 

(1 * 7^5) mod 6 + (2 * 7^4) mod 6 + (3 * 7^3) mod 6 + (4 * 7^2) mod 6 + (5 * 7^1) mod 6 + (6 * 7^0) mod 6

 

으로 바꿀 수 있다.  (1 * 7^5) mod6 만 따로 살펴보자.

 

1*7^5 = (1*7*7*7*7*7) mod 6 = 1 mod 6 * (7 mod 6) * 5 = 1 mod 6

 

이다. (2 * 7^4) mod 6, (3 * 7^3) mod 6, (4 * 7^2) mod 6, (5 * 7^1) mod 6,

(6 * 7^0) mod 6도 동일한 과정으로 2 mod 6, 3 mod 6, 4 mod 6, 5 mod 6,

6 mod 6으로 바꿀 수 있으므로 결국 123456(7) mod 6은

 

1 mod 6 + 2 mod 6 + 3 mod 6 + 4 mod 6 + 5 mod 6 + 6 mod 6 = (1 + 2 + 3 + 4 + 5 + 6) mod 6

 

으로 바꿀 수 있다. 다른 진법의 수도 동한 과정으로 주어진 식을 모든 자릿수를 더한 뒤에 b-1 로 나눈 나머지를 구하는 식으로 치환할 수 있다. 따라서 주어진 수를 scanf를 통해 문자열로 받은 뒤, 각 문자를 모두 더해서 이를 b-1과 나머지 연산하면 답을 구할 수 있다.

 

 

전체 코드는 아래와 같다.

 

#include <cstdio>
#include <cstring>
int main() { //3944 나머지 계산
	int t;
	cin >> t;
	
	while (t--) {
		int i, b, sum=0;
		char d[10000000];
		scanf("%d", &b);
		scanf("%s", d);

		for (i = 0; i < strlen(d); i++) {
			sum += d[i] - 48;
		}
		printf("%d\n", sum % (b-1));
	}
}