BOJ)13212 Random

문제: icpc.me/13212

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

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

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

#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;
}