1 (4375번)
https://www.acmicpc.net/problem/4375
이전풀이
BigInteger를 이용해 풀었으나 성능이 좋지 않았다.- 이전풀이
문제설명
- 1로만 이루어진 n의 배수를 찾는다는 것은 1로만 이루어진 숫자
예)111를n으로 나눴을 때 나누어 떨어지는가? 를 묻는 것이다. - 예제 출력의 3은
111이 되고 6은111111, … 이 된다는 뜻이 된다.
풀이방법
Modular연산을 이용해 풀 수 있는 문제이다. 1)(A+B)%C는 ((A%C) + (B%C))%C와 같다2)(A×B)%C는 ((A%C) × (B%C))%C와 같다- 위 두가지 조건을 이용해 문제를 풀 수 있다.
- 첫 번째 조건을 보면
(A+B)%C는 ((A%C) + (B%C))%C와 같다고 하였으므로 결과는 아래와 같다.1 2 3 4 5 6 7 8 9 10 11
1) A = 1%X 2) B = 11%X 3) C = 111%X 4) D = 1111%X 에서 A는 (0+1)%X = 1 B는 (10+1)%X = (((A*10)%X) + (1%X))%X C는 (110+1)%X = (((B*10)%X) + (1%X))%X D는 (1110+1)%X = (((C*10)%X) + (1%X))%X ... 이 된다.
- 위의 설명에 따라
1,11,111,1111, …을 순차적으로 구해주면 답이 나오게 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
StringBuilder sb = new StringBuilder();
int n = 0;
int remainder = 1;
int count = 1;
while ((str = br.readLine()) != null) {
n = Integer.parseInt(str);
if (n == 1) {
System.out.println(1);
continue;
}
count = 1;
remainder = 1;
while (remainder != 0) {
remainder = (10 * remainder + 1) % n;
count++;
}
sb.append(count).append('\n');
}
System.out.println(sb);
}
}
Comments powered by Disqus.