/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 532.0 KiB

Code

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int N, X;
        cin >> N >> X;
        
        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        
        // Get the prime factors of X
        unordered_map<int, int> xFactors = getPrimeFactors(X);
        
        // Prepare prefix factor counts for only the primes in xFactors
        unordered_map<int, vector<int>> prefixFactorCount;
        for (const auto& [prime, _] : xFactors) {
            prefixFactorCount[prime] = vector<int>(N + 1, 0);
        }
        
        // Compute prefix factor counts
        for (int i = 1; i <= N; ++i) {
            auto currentFactors = getPrimeFactors(A[i - 1]);
            for (const auto& [prime, _] : xFactors) {
                prefixFactorCount[prime][i] = prefixFactorCount[prime][i - 1] + currentFactors[prime];
            }
        }
        
        int Q;
        cin >> Q;
        while (Q--) {
            int L, R;
            cin >> L >> R;
            L--; R--;  // Convert to 0-based indexing
            
            bool divisible = true;
            for (const auto& [prime, requiredCount] : xFactors) {
                int factorCountInRange = prefixFactorCount[prime][R + 1] - prefixFactorCount[prime][L];
                if (factorCountInRange < requiredCount) {
                    divisible = false;
                    break;
                }
            }
            cout << (divisible ? "Yes" : "No") << '\n';
        }
    }
    
    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:03:23
Judged At
2024-11-05 16:03:23
Judged By
Score
10
Total Time
4ms
Peak Memory
532.0 KiB