結果

問題 No.854 公平なりんご分配
ユーザー xuzijian629
提出日時 2019-07-26 21:42:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,711 bytes
コンパイル時間 2,334 ms
コンパイル使用メモリ 202,264 KB
最終ジャッジ日時 2025-01-07 07:47:36
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 RE * 59 TLE * 1 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector<bool> prime(20001, true);
int mp[20001];
vector<int> primes;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    prime[0] = prime[1] = false;
    for (int i = 2; i < 20001; i++) {
        if (prime[i]) primes.push_back(i);
        else continue;
        for (int j = 2; i * j < 20001; j++) {
            prime[i * j] = false;
        }
    }

    int N = primes.size();
    for (int i = 0; i < N; i++) mp[primes[i]] = i;

    int n;
    cin >> n;
    vector<vector<int>> cnt(N, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        for (int j = 2; j * j <= a; j++) {
            while (a % j == 0) {
                a /= j;
                cnt[mp[j]][i]++;
            }
        }
        if (a > 1) {
            cnt[mp[a]][i]++;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= n; j++) {
            cnt[i][j] += cnt[i][j - 1];
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int p, l, r;
        cin >> p >> l >> r;
        bool ok = true;
        for (int a = 2; a * a <= p; a++) {
            if (p % a == 0) {
                int c = 0;
                while (p % a == 0) {
                    p /= a;
                    c++;
                }
                int k = cnt[mp[a]][r] - cnt[mp[a]][l - 1];
                if (c > k) {
                    ok = false;
                    break;
                }
            }
        }
        if (p > 1) {
            int k = cnt[mp[p]][r] - cnt[mp[p]][l - 1];
            if (1 > k) {
                ok = false;
            }
        }
        cout << (ok ? "Yes" : "NO") << endl;
    }
}
0