結果

問題 No.854 公平なりんご分配
コンテスト
ユーザー yuriko32
提出日時 2026-03-16 10:32:01
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,885 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 765 ms
コンパイル使用メモリ 94,928 KB
実行使用メモリ 63,364 KB
最終ジャッジ日時 2026-03-16 10:32:14
合計ジャッジ時間 5,854 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 90 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


const int MAX_A = 2000;
const int MAX_N = 100005;

int min_prime[MAX_A + 1];
int primes[303];
int p_count = 0;


unsigned short pref[MAX_N][303];
int zero_pref[MAX_N];

void sieve() {
    for (int i = 2; i <= MAX_A; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes[p_count++] = i;
        }
        for (int j = 0; j < p_count && primes[j] <= min_prime[i] && i * primes[j] <= MAX_A; ++j) {
            min_prime[i * primes[j]] = primes[j];
        }
    }
}

void solve() {
    int N;
    if (!(cin >> N)) return;

    sieve();

    for (int i = 1; i <= N; ++i) {
        int a;
        cin >> a;
        
        for (int j = 0; j < p_count; ++j) pref[i][j] = pref[i-1][j];
        zero_pref[i] = zero_pref[i-1];

        if (a == 0) {
            zero_pref[i]++;
        } else {
            int temp = a;
            for (int j = 0; j < p_count; ++j) {
                if (primes[j] * primes[j] > temp) break;
                while (temp % primes[j] == 0) {
                    pref[i][j]++;
                    temp /= primes[j];
                }
            }
            if (temp > 1) {
                int idx = lower_bound(primes, primes + p_count, temp) - primes;
                if (idx < p_count && primes[idx] == temp) {
                    pref[i][idx]++;
                }
            }
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        long long P; 
        int L, R;
        cin >> P >> L >> R;

        // 1. Ưu tiên kiểm tra số 0
        if (zero_pref[R] - zero_pref[L-1] > 0) {
            cout << "Yes\n";
            continue;
        }

        // 2. Nếu P = 1
        if (P == 1) {
            cout << "Yes\n";
            continue;
        }

        bool ok = true;
        long long temp_p = P;

        for (int j = 0; j < p_count; ++j) {
            if (1LL * primes[j] * primes[j] > temp_p) break;
            if (temp_p % primes[j] == 0) {
                int required = 0;
                while (temp_p % primes[j] == 0) {
                    required++;
                    temp_p /= primes[j];
                }
                int available = pref[R][j] - pref[L-1][j];
                if (available < required) {
                    ok = false;
                    break;
                }
            }
        }

        if (ok && temp_p > 1) {
            if (temp_p <= MAX_A) {
                int idx = lower_bound(primes, primes + p_count, (int)temp_p) - primes;
                int available = pref[R][idx] - pref[L-1][idx];
                if (available < 1) ok = false;
            } else {
                ok = false;
            }
        }

        cout << (ok ? "Yes" : "NO") << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
0