2024 - 06 - 04 C++ 코딩테스트 10주완성 D+13

1 - 백준 4375 문제

 

시작하기에 앞서 이 문제의 핵심은 모듈러 분배 법칙에 있다.

(A * B + C * D) % F = ((A * B) % F + (C * D) % F) % F

 

라는 공식이다. 이를 이용하여 시간복잡도를 짧게 만들 수 있다.

 

 

2와 5로 나누어 떨어지지 않는 자연수 n을 입력받아

 

각 자리수가 1인수의 자릿수를 출력하는 문제

 

입력받은 10의 자리수를 올려서 더해줄 임의의 변수 cnt와

 

자릿수를 카운트해줄 ret를 이용하여

 

먼저 cnt = 1 와 ret = 1 으로 초깃값을 정해준 다음에 

 

cnt = (10 * cnt ) + 1 라는 증감식을 써준다.

 

위에 식을 계산하면 1, 10 + 1 , 110 + 1 , 1110 + 1 으로 전부 각 자리수가 1인 1 , 11, 111, 1111 ... 등의 숫자가 나오게 된다.

 

그리고 더하여 줄때마다 자릿수를 더하여 주어야하기 때문에 ret++ 를 추가한다.

 

cnt 를 처음 입력받은 자연수로 나누었을 때, 나머지가 0이 되면 배수인것이다.

 

따라서 나머지가 0이 될때 자릿수인 ret을 출력시켜주면 된다.

 

그리고 모듈러 법칙에서  ret  % a  를 해주어도 다시 %a를 나누었을 때 나머지 값은 똑같으므로 나누어 준다.

 

#include <bits/stdc++.h>

using namespace std;

long long a;

int main()
{

	while (cin >> a && a != EOF)
	{
		long long cnt = 1, ret = 1;
		while (true)
		{				
			if (ret % a == 0)
			{
				cout << cnt << endl;
				break;
			}
			
			else
			{
				ret = ret * 10 + 1;
				ret %= a;
				cnt++;
			}
			
		}
	}
	return 0;
}