1837번: 암호제작
원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로
www.acmicpc.net
BigInteger를 사용하는 문제입니다.
P는 소수의 곱으로 이루어져있지만 10^100이라는 수가 입력으로 주어집니다.
K는 P가 좋은 암호인지, 좋지 않은 암호인지 구별하는 수이며 1000000까지 주어집니다.
P를 나타내는 소수 p, q 중에 하나라도 K보다 작으면 이 암호P는 좋지 않은 암호입니다.
하지만 P가 너무 큰 수이기 때문에 소수를 직접 구할 수 없으므로 K범위 내의 소수를 모두 구하여
구한 소수들 중 P와 나머지 연산을 해서 0이 되는 수가 있으면 BAD, 없으면 GOOD를 출력하였습니다.
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static BigInteger P, K;
static boolean sosuchk[] = new boolean[1000001];
static Set<BigInteger> sosu = new TreeSet<>();
static int k;
static void func() {
Iterator<BigInteger> iter = sosu.iterator();
while (iter.hasNext()) {
BigInteger a = iter.next();
if (a.compareTo(K) >= 0)
break;
if (P.mod(a).equals(new BigInteger("0"))) {
System.out.println("BAD " + a);
return;
}
}
System.out.println("GOOD");
}
static void init() {
for (int i = 2; i <= 1000000; i++) {
if (sosuchk[i])
continue;
sosu.add(new BigInteger(Integer.toString(i)));
for (int j = 2; i * j <= 1000000; j++) {
if (sosuchk[i * j])
continue;
sosuchk[i * j] = true;
}
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
P = new BigInteger(st.nextToken());
k = Integer.parseInt(st.nextToken());
K = new BigInteger(Integer.toString(k));
}
public static void main(String[] args) throws Exception {
init();
input();
func();
}
}
|
cs |
'algorithm > Math' 카테고리의 다른 글
| boj 13136 Do Not Touch Anything (0) | 2022.10.25 |
|---|---|
| boj 15740 A+B - 9 (0) | 2021.01.31 |
| boj 1002 터렛 (0) | 2021.01.27 |