結果

問題 No.854 公平なりんご分配
コンテスト
ユーザー yuriko32
提出日時 2026-03-16 10:09:38
言語 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,792 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 658 ms
コンパイル使用メモリ 102,388 KB
実行使用メモリ 126,592 KB
最終ジャッジ日時 2026-03-16 10:10:00
合計ジャッジ時間 15,696 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 12 RE * 80
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <map>

using namespace std;


const int MAX_A = 2000;
const int MOD = 1000000007;


vector<int> primes;
int min_prime[MAX_A + 1];


void sieve() {
    for (int i = 2; i <= MAX_A; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > min_prime[i] || i * p > MAX_A) break;
            min_prime[i * p] = p;
        }
    }
}

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

    int N, Q;
    cin >> N >> Q;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];

    sieve();
    int num_primes = primes.size();


    vector<vector<int>> prefix_counts(N + 1, vector<int>(num_primes, 0));

    for (int i = 1; i <= N; ++i) {
       
        prefix_counts[i] = prefix_counts[i - 1];
        
        int temp = A[i];
        if (temp == 0) continue; 

        
        for (int j = 0; j < num_primes; ++j) {
            int p = primes[j];
            if (p * p > temp) break;
            while (temp % p == 0) {
                prefix_counts[i][j]++;
                temp /= p;
            }
        }
        if (temp > 1) {
            for (int j = 0; j < num_primes; ++j) {
                if (primes[j] == temp) {
                    prefix_counts[i][j]++;
                    break;
                }
            }
        }
    }

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

       
        if (P == 1) {
            cout << "Yes\n";
            continue;
        }

        bool possible = true;
        int temp_p = P;

       
        for (int j = 0; j < num_primes; ++j) {
            int p = primes[j];
            if (p * p > temp_p) break;
            
            int count_in_p = 0;
            while (temp_p % p == 0) {
                count_in_p++;
                temp_p /= p;
            }

            if (count_in_p > 0) {
               
                int count_in_range = prefix_counts[R][j] - prefix_counts[L - 1][j];
                if (count_in_range < count_in_p) {
                    possible = false;
                    break;
                }
            }
        }

      
        if (possible && temp_p > 1) {
            bool found = false;
            for (int j = 0; j < num_primes; ++j) {
                if (primes[j] == temp_p) {
                    int count_in_range = prefix_counts[R][j] - prefix_counts[L - 1][j];
                    if (count_in_range < 1) possible = false;
                    found = true;
                    break;
                }
            }
            
            if (!found) possible = false;
        }

        if (possible) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}
0