/ SeriousOJ /

Record Detail

Compile Error

foo.cc: In function 'int main()':
foo.cc:96:21: error: 'queries' was not declared in this scope
   96 |             int L = queries[q].first - 1;
      |                     ^~~~~~~

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

// Function to factorize X and get its prime factors with powers
unordered_map<int, int> getPrimeFactors(int num) {
    unordered_map<int, int> prime_factors;
    for (int i = 2; i <= sqrt(num); i++) {
        while (num % i == 0) {
            prime_factors[i]++;
            num /= i;
        }
    }
    if (num > 1) {
        prime_factors[num]++;
    }
    return prime_factors;
}

// Function to get prime factor counts using a sieve up to a maximum element in A
vector<int> sieveSmallestPrimeFactor(int maxA) {
    vector<int> spf(maxA + 1); // spf[x] will store smallest prime factor of x
    for (int i = 2; i <= maxA; i++) {
        if (spf[i] == 0) { // i is prime
            for (int j = i; j <= maxA; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
    return spf;
}

// Function to use spf to factorize any number
unordered_map<int, int> factorizeWithSieve(int num, const vector<int>& spf) {
    unordered_map<int, int> factors;
    while (num > 1) {
        int prime = spf[num];
        factors[prime]++;
        num /= prime;
    }
    return factors;
}

int main() {
    int T;
    cin >> T;
    
    // Determine maximum value of A[] to precompute smallest prime factors
    int maxA = 0;
    vector<vector<int>> test_cases;
    vector<int> maxAs(T);
    
    for (int t = 0; t < T; ++t) {
        int N, X;
        cin >> N >> X;
        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
            maxA = max(maxA, A[i]);
        }
        
        int Q;
        cin >> Q;
        vector<pair<int, int>> queries(Q);
        for (int i = 0; i < Q; ++i) {
            cin >> queries[i].first >> queries[i].second;
        }
        test_cases.push_back({N, X});
        maxAs[t] = maxA;
    }
    
    vector<int> spf = sieveSmallestPrimeFactor(maxA);
    
    for (int t = 0; t < T; ++t) {
        int N = test_cases[t][0];
        int X = test_cases[t][1];
        vector<int> A(N);
        unordered_map<int, int> xFactors = getPrimeFactors(X);
        
        unordered_map<int, vector<int>> prefixFactorCount;
        for (auto &[prime, _] : xFactors) {
            prefixFactorCount[prime] = vector<int>(N + 1, 0);
        }
        
        for (int i = 1; i <= N; ++i) {
            unordered_map<int, int> currentFactors = factorizeWithSieve(A[i - 1], spf);
            for (auto &[prime, _] : xFactors) {
                prefixFactorCount[prime][i] = prefixFactorCount[prime][i - 1] + currentFactors[prime];
            }
        }
        
        int Q = test_cases[t][2];
        for (int q = 0; q < Q; ++q) {
            int L = queries[q].first - 1;
            int R = queries[q].second - 1;
            
            bool divisible = true;
            for (auto &[prime, requiredCount] : xFactors) {
                int factorCountInRange = prefixFactorCount[prime][R + 1] - prefixFactorCount[prime][L];
                if (factorCountInRange < requiredCount) {
                    divisible = false;
                    break;
                }
            }
            cout << (divisible ? "Yes" : "No") << endl;
        }
    }
    
    return 0;
}

Information

Submit By
Type
Pretest
Problem
P1128 Roy and Product
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:02:28
Judged At
2024-11-05 16:02:28
Judged By
Score
0
Total Time
0ms
Peak Memory
0 Bytes