문제 설명
N의 배수 중에 1로만 이루어진 수 중에 가장 작은 자릿수를 구하는 문제입니다.
풀이
1로만 이루어진 수를 만들어가며 N의 배수인지 확인해 주면 됩니다.
불가능할 경우 -1을 출력해야 합니다.
N으로 나눠지지 않고 무한 루프에 빠질 때 불가능합니다.
N의 나머지가 0~N-1까지 나올 수 있는데 0이 나오지 않고 다른 1~N-1 숫자가 두 번 이상 나오게 될 경우 무한 루프에 빠지게 됩니다.
즉, 나머지가 0이 아닌 사이클이 존재할 경우 불가능합니다.
그럼 1로만 이루어진 수를 만들어가며 확인을 할 건데 최악으로 N이 최대 10만이기 때문에 1~10만까지 한 번씩 나오고 마지막에 0이 나온다 가정하면 long long 범위는 가뿐히 넘어버립니다.
그래서 정직하게 수를 만들어가며 답을 구할 수 없습니다.
저희가 원하는 건 N의 배수를 구하는 것이 아니라 N의 배수의 자릿수를 구하는 것입니다.
그러므로 수를 구하지 않고 자릿수를 하나씩 올려가면서 N으로 나누었을 때 나머지가 0이면 정답을 출력하시면 됩니다.
1로만 이루어져 있는 수로 다음 수를 구하고 N으로 나눈 나머지나 나머지로 다음 수를 구하고 N으로 나눈 나머지가 같습니다.
(1111 * 10 + 1) % 7 = 2
((1111 % 7) * 10 + 1) % 7 = 2
나머지만 중요하기 때문에 나머지만 가져가서 연산을 하겠습니다.
A = (A * 10 + 1) % N
A % N == 0 일 때 N의 배수이므로 자릿수를 출력하면 됩니다.
이제 불가능한 경우를 봐야겠죠..?
0이 아닌 사이클이 존재하면 불가능하기 때문에 check 배열 하나 만들어서 같은 수가 또 나오면 그때 불가능을 출력하면 되지만 그보다 더 간단하게 구할 수 있습니다.
(A * 10 + 1) % N = (B * 10 + 1) % N
이 성립하게 되면 사이클이 존재합니다.
(0 <= A < B < N, C > 0, N은 자연수)
(A * 10 + 1) + C * N = (B * 10 + 1)
C * N = (B * 10 + 1) - (A * 10 + 1)
N = (B - A) * 10 / C
A, B, C가 위 조건에 만족할 때 자연수인 N을 찾겠습니다.
N이 자연수가 되려면 (B - A) % C = 0 이거나 10 % C = 0 이어야 합니다.
(B - A) % C = 0일 때는 N이 10의 배수이고
10 % C = 0이 되려면 C가 1,2,5,10일 때 가능한데
C = 10 일 때, (B - A) = N이 위 조건 A, B 범위(0 <= A < B < N)를 고려했을 때 성립하지 않기 때문에 제외합니다.
그러면 C가 가능한 수는 1,2,5입니다.
그러면 N은 2,5,10의 배수가 됩니다.
2, 5의 배수들은 끝자리가 1인 숫자들의 배수가 될 수 없기 때문에 0인 사이클이 존재하지 않습니다.
결국 0이 아닌 사이클이 존재합니다.
그러므로 N은 2, 5의 배수 일 때 불가능합니다.
저렇게 하지 않고 문제를 봐도 2, 5의 배수들은 불가능하겠구나 생각하지만…
과정을 그냥 글로 한 번 남겨보고 싶었습니다 하핳
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main(){
FIO;
int n;
cin >> n;
if(!(n % 2 && n % 5)) return cout << -1 << '\n',0;
for(int i=1, j = 0;;i++){
j = (10 * j + 1) % n;
if(!(j % n)) {
cout << i << '\n';
break;
}
}
return 0;
}