티스토리 뷰

알고리즘 관련/BOJ

BOJ)13212 Random

JASON 자손9319 2017. 10. 16. 15:53

문제: icpc.me/13212


1)주어지는 수의 1을 제외한 소인수가 모두 K보다 크면서 2)연속되는 같은 숫자가 4개 이상이 아닌지 확인하는 문제이다.


2)의 조건은 10으로 나눠주면서 연속되는 자리수의 개수를 세주면 되고


1)의 조건은 sqrt(maxNumber)보다 작은 모든 소수를 구해준 뒤 그 수들로 나눠지는 가장 작은 수가 K보다 큰지 여부를 확인해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll n, k, num;
bool p[100010];
vector<ll> v;
int main() {
    scanf("%lld%lld"&n, &k);
    for (int i = 2; i <= 100000; i++) {
        if (p[i])continue;
        for (int j = i + i; j <= 100000; j += i) 
            p[j] = 1;
    }
    for (int i = 2; i <= 100000; i++)
        if (!p[i])v.push_back(i);
    for (int i = 0; i < n; i++) {
        scanf("%lld"&num);
        ll y = -1;
        for (auto j : v) {
            if (sqrt(num) < j)break;
            if (!(num%j)) {
                y = j;
                break;
            }
        }
        if (y == -1)y = num;
        ll flag = 0;
        if (y <= k)
            flag = 1;
        ll prev = num % 10;
        num /= 10;
        ll cnt = 1;
        while (num) {
            if (prev == num % 10) cnt++;
            else {
                prev = num % 10;
                cnt = 1;
            }
            num /= 10;
            if (cnt > 3)
                flag = 1;
        }
        printf("%s\n", flag ? "NO" : "YES");
    }
    return 0;
}
cs


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

BOJ)5849 Cow Crossings  (0) 2017.10.24
BOJ)2023 신기한 소수  (0) 2017.10.16
BOJ)13212 Random  (0) 2017.10.16
BOJ)13213 Binary Roads  (0) 2017.10.16
BOJ)11442 홀수번째 피보나치 수의 합  (0) 2017.10.14
BOJ)11443 짝수번째 피보나치 수의 합  (0) 2017.10.14
댓글
댓글쓰기 폼