[백준] 모듈러 연산 정의 및 활용

목차

 

 

모듈러의 정의

어떤 정수 A를 다른 정수 N으로 나누면 나오는 나머지를 말한다.

 

모듈러 연산의 여러 성질들

 

분배 법칙의 성립

(A +(-) B) mod C = (A mod C +(-) B mod C) mod C

(A * B) mod C = (A mod C * B mod C) mod C

 

 

덧셈, 뺄셈, 곱셈에 관련된 성질

a와 b로 m으로 나눈 나머지가 같고 c와 d를 m으로 나눈 나머지가 같으면 

a ± c 와 b ± d 를 m으로 나눈 나머지도 같다.

예)

49 <=> 1 (mod 8) 37 <=> 5 (mod 8) 

86 <=> 6(mod 8)

 

 

거듭 제곱의 성질

a와 b를 m으로 나눈 나머지가 동일 하다면,

각 숫자를 동일하게 거듭제곱한 숫자를 m으로 나눈 나머지도 동일하다

예)

77 <=> 7 (mod 8)

77 ^ 10 <=> 7 ^ 10 (mod 8)

 

모듈러 연산을 이용한 대표적인 문제

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

 

 

코드 구현

using namespace std;


int main() {
	long long int n, d =1, cnt=1;
	while (scanf("%d", &n) != EOF)  {   //계속해서 입력
		d = 1; cnt = 1;
		while (true) {
			if (d % n == 0)  //나누어지면 탈출
				break;  
			d = (d * 10 + 1);
			d %= n;   //모듈러 연산의 성질 이용
			cnt++;   //연산수를 세줌
		}
		printf("%d\n", cnt);
	}

}