結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

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

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

    prime[0] = prime[1] = false;
    for (int i = 2; i < 2001; i++) {
        if (prime[i]) primes.push_back(i);
        else continue;
        for (int j = 2; i * j < 2001; 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 : primes) {
            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) ok = false;
        cout << (ok ? "Yes" : "NO") << '\n';
    }
}
0