BOJ 4375 : 1

문제에서 2 또는 5로 나누어 떨어지지 않는 정수만 주어진다 했으니 비둘기집 원리에 의해 항상 답이 존재함을 알 수 있다.

 

우리는 1을 붙이지 않고 나머지의 성질을 이용하여 풀 수 있다.

=> (a+b)%MOD = a%MOD + b%MOD

=> (a*b)%MOD = ((a%MOD)*(b%MOD))%MOD

 

이를 이용해 배수를 하나의 식을 통해 확인할 수 있다.

=> a = (a*10+1)%n

a가 0일 때까지 저 식을 계산해준다.

답은 저 식을 계산해준 횟수이다.

 

#include <bits/stdc++.h>
#define MEM 500
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll t,n,m,o,p;
main()
{
    sanic;
    while(cin >> t){
        if(t==1){
            cout << 1 << '\n';
            continue;
        }
        int tmp=1;
        while(((tmp*10+1)%t))
            p++, tmp = (tmp*10+1)%t;
        cout << p+2 << '\n';
        p=0;
    }
}