[백준 c++] 4375 1

문제 설명

https://www.acmicpc.net/problem/4375
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수의 자리수를 출력하는 문제다.

아이디어

입력이 계속해서 주어지기 때문에 while(cin>>n)를 이용해야 한다.
long long을 사용해도 수가 계속 커지다보면 범위를 넘어갈 수 있기 때문에 단순히 나누기를 하면 안된다.

모듈러 연산 활용
(a*b) mod N = (a mod N * b mod N) mod N
중간 중간 %처리를 해줘도 그 결과 값은 같기 때문에 이를 이용해서 수가 커지는 것을 방지할 수 있다.

전체 코드

#include <iostream>
using namespace std;

int n;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    while (cin >> n)
    {
        int a = 1;
        int cnt = 1;
        while (1)
        {
            if (a % n == 0)
            {
                cout << cnt << "\n";
                break;
            }
            a = a * 10 + 1;
            a %= n;
            cnt++;
        }
    }
}