[BOJ/C++] 4375. 1

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

4375번: 1

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

해결 방법

1. 처음에 문제를 이해하는 것이 어려웠다.

 조건 1. 입력에는 2와 5로 나누어 떨어지지 않는 정수 (1 ≤ n ≤ 10000)이 주어졌다. (테스트 케이스를 만들때 신경 써야 할 것)

 조건 2. 1로 이루어진 n의 배수의 의미는 숫자는 1,11,111,1111,11111..... 이렇게 늘어나는 것이고 n의 배수는 입력 받은 수의 배수인지 나눠서 검증하는 것이다. 

 

 방법. 나머지의 정리를 생각하면 ((M % N) * 10 + 1) % N 을 반복하는 방법을 이용한다. 

        그림으로 보면 다음과 같다.

 

 선이 조금 엇나갔는데 아무튼 나눌 수 n은 7로 가정하고 우리가 생각하는 수 m은 1,11,111,1111,11111로 증가한다고 생각하면 된다.

 

PREV에 * 10 + 1을 하고 계속해서 N으로 나눈 나머지에서 0이 나올때까지 검증하고 그 자리수는 count를 세어준 것과 같다.

// Code Plus BasicA
// 0x00. Math
// Written by Rylah
// Written Date : 2022.01.13
// https://minteul.tistory.com/303
// https://www.acmicpc.net/source/37480110

// 4375. 1
// m : last add 1 , maybe it's very very high num. use long long.
// n : mod number
// count : m length is count iter num

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	
	while (cin >> n) // if is cin infinite looping
	{
		int count = 1;
		long long m = 1;
		while (m % n != 0)
		{
			m = m * 10 + 1;
			m %= n;
			count++;
		}
		cout << count << '\n';
	}
	return 0;
}