개요

PS 문제에 자주 나오는 모듈러에 대해 알아보자. 보통 기본 타입으로 표현하기에는 너무 큰 값이 나올 때 모듈러가 등장하게 된다

모듈러 연산

모듈러 연산은 즉 나머지 연산을 의미한다

N mod m은 N을 m으로 나눈 나머지를 의미하며
결과는 [0, m-1] 사이의 값이 된다
코드에서는 '%'로 표현

기본 성질

모듈러 연산을 할 때 중요하게 기억해둬야 하는 것이 있다

• (a + b) % m = ((a % m) + (b % m)) % m
• (a - b) % m = ((a % m) - (b % m)) % m
• (a x b) % m = ((a % m) x (b % m)) % m

즉, 두 수를 더하고, 빼고, 곱한 다음 mod 하는거랑 각각의 수를 mod한 것을 더하고, 빼고, 곱한 다음 다시 mod 한 거랑 결과가 같다는 것이다

예를 들면 a가 12이고 b가 10일 때 m이 3이라고 하자

(12 + 10) % 3 = ((12 % 3) + (10 % 3)) % 3
1 = (0 + 1) % 3 = 1

이런 성질을 이용해 문제를 푸는 경우가 많으니 꼭 기억해두자

그리고 나눗셈의 경우에는 정의되지 않는다! 왜냐면 정수 나눗셈은 나머지를 보존하지 않기 때문이다

음수를 mod하는 경우는 어떻게 될까?
C++의 경우 N mod m에서 N이 음수일 때에는 %의 결과가 N의 부호를 따라간다. 그래서 N을 양수로 생각하고 mod를 구한 다음 부호를 붙여주면 된다

하지만 mod의 값이 양수가 나오게 하고 싶은 경우에는
(N % m + m) % m의 공식을 사용하면 된다

문제

백준 4375번

문제

풀이

이 문제를 가장 처음 봤을 때에는 그냥 1, 11, 111, ... 반복해가면서 n으로 나눠지는지 확인하면 되는거 아니야?

라고 생각하면 안되는게 long long보다 더 커버리는 숫자가 등장해버리니까 안 된다

위의 모듈러 연산을 이용하는 방법을 생각해보면 n을 어떻게든 오버플로우가 안나게 해야한다

매 입력마다 초기 값을 1로 두고, 자릿수도 1로 설정해둔 다음 로직을 실행하자

1에서 11을 표현할 방법은 (1 10 + 1)이고, 11에서 111을 표현할 방법은 (11 10 + 1), ... 이렇게 가면 (변수 * 10 + 1)로 나타낼 수 있다

그리고 나서 그 값을 n으로 mod한 값을 저장한다

n이 3이라고 생각해보자

1 % 3은 0이 아니므로 자리수를 증가시킨다
(1 x 10 + 1) % 3 = 2(11)
(2 x 10 + 1) % 3 = 0(111)

코드

#include <bits/stdc++.h>

using namespace std;

void Input() 
{
	
}

void Solve()
{
	int n;

	while (cin >> n)
	{
		int current = 1;
		int count = 1;

		while ((current % n) != 0)
		{
			current = (current * 10 + 1) % n;
			count++;
		}

		cout << count << '\n';
	}
}

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

	Input();
	Solve();

	return 0;
}