본문 바로가기

알고리즘 관련/BOJ

BOJ)1837 암호제작

문제: icpc.me/1837


P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다.


우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤


P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다.


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
#include <cstdio>
#include <algorithm>
using namespace std;
char a[110];
int k, p[2000000];
bool chk(const char *s, int p) {
    int ret = 0;
    for (int i = 0; s[i]; i++)
        ret = (ret * 10 + s[i] - '0') % p;
    return !ret ? true : false;
}
int main() {
    scanf("%s%d"&a, &k);
    for (int i = 2; i < 2000000; i++) {
        if (p[i])continue;
        for (int j = i + i; j < 2000000; j += i)
            p[j] = true;
    }
    int r = 0, pp = 987654321;
    for (int i = 2; i <= k; i++) {
        if (p[i])continue;
        if (chk(a, i)) {
            r = 1;
            pp = min(pp, i);
        }
    }
    printf("%s ", r ?  "BAD" : "GOOD");
    if (r)
        printf("%d\n", pp);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13538 XOR 쿼리  (0) 2017.06.05
BOJ)1322 X와K  (0) 2017.06.05
BOJ)14577 일기예보  (0) 2017.06.04
BOJ)6850 Cows  (0) 2017.06.02
BOJ)2254 감옥 건설  (0) 2017.06.01