백준 - 4375 1 c++ (모듈러연산 방식)

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

해당 문제는 처음에 이렇게 풀었다

숫자를 직접 만들고 전부 계산하는방식으로 말이다

#include <iostream>
#include <string>

using namespace std;
int num;
int main()
{
	while (cin >> num)
	{
		string s = "1";
		while (true)
		{
			long long temp = 0;
			for (char c : s)
				temp = temp * 10 + (c - '0');

			if (temp % num == 0)
			{
				cout << s.size() << '\n';
				break;
			}
			s += "1";
		}
	}
	return 0;
}

 

그랬더니 오버플로우 + 시간초과가 나왔다

 

이럴떈 정수론의 "모듈러 연산" 을 사용하면된다

모듈러 연산의 공식은 이와 같다

 

• ( a + b ) % n = ( a % n + b % n ) % n
• ( a * b ) % n = ( a % n * b % n ) % n

모듈러 연산을 적용하면 이와같다

#include <iostream>

using namespace std;
int num;
long long cnt, temp;
int main()
{
	while (cin >> num)
	{
		int cnt = 1, temp = 1;
		while (true)
		{
			if (cnt % num == 0)
			{
				cout << temp << '\n';
				break;
			}
			else
			{
				//원래 공식 = cnt = cnt * 10 + 1;
				//모듈러 공식
				cnt = (cnt * 10 + 1) % num;
				temp++;
			}
		}
	}
	return 0;
}

 

피보나치 수열 같은 값이 엄청나게 커지는 경우라던가

연산이 엄청나게 반복될때 사용하면될꺼같다