취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3944번 문제인 나머지 계산이다.
문제는 아래 링크를 확인하자.

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

10진수의 9의 배수 판정법으로 주어진 수의 모든 각 자릿수의 합이 9의 배수인지 확인하는 것이 있다. 이를 배수가 아닌 모든 나머지에 대해, 그리고 2 이상의 모든 진법에 대해 확장해보자.

$b=B-1$이라 할 때, $B$진법 수 $10000000$은 $B$진법 수 $bbbbbbb+1$과 같으므로 $10000000$을 $b$로 나눈 나머지는 1이 됨을 관찰하자. 이는 꼭 여덟번째 자리에만 해당하는 관찰이 아닌 임의의 자리에 적용될 수 있는 관찰이다.

따라서 $B$진법 수를 $b$로 나눈 나머지는 각 자리를 나타내는 수의 합을 $b$로 나눈 나머지와 같음을 알 수 있다.

위 관찰을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int N; string s;
int total;

void solve() {
	total = 0;
	cin >> N >> s;
	for (auto &l : s) total += l - '0';
	cout << total % (N - 1) << '\n';
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}