[백준 4375] 모듈로 연산이란?

모듈로 연산이란?

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산

정수론에서 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법

 

A mod C = B mod C 라면, A와 B는 사실상 같은 수다

이 문제에서는,

i mod input = (i mod input) % input이 된다

그러면 long long int의 범위를 넘어가지 않고, 시간 초과가 나지 않고 문제를 풀 수 있게 된다

 

#include <iostream>
using namespace std;

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int input;
	
	while (cin >> input) {
		int i = 1;
		int result = 1;
		while (1) {
			if(i % input == 0){
				break;
			}
			else {
				result++;
				i = i * 10 + 1;
				i = i% input;
			}
		}
		cout << result << "\n";
	}

	return 0;
}