/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 105ms 836.0 KiB
#4 Accepted 88ms 788.0 KiB
#5 Accepted 113ms 680.0 KiB
#6 Accepted 134ms 836.0 KiB
#7 Accepted 107ms 948.0 KiB
#8 Accepted 121ms 1.02 MiB
#9 Accepted 128ms 1.02 MiB
#10 Accepted 157ms 2.27 MiB
#11 Accepted 115ms 1.684 MiB
#12 Accepted 125ms 1.77 MiB
#13 Accepted 158ms 1020.0 KiB
#14 Accepted 85ms 1.02 MiB
#15 Accepted 166ms 636.0 KiB
#16 Accepted 159ms 836.0 KiB
#17 Accepted 124ms 836.0 KiB
#18 Time Exceeded ≥1599ms ≥796.0 KiB
#19 Time Exceeded ≥1508ms ≥820.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
Submission
Problem
P1128 Roy and Product
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:03:29
Judged At
2024-11-05 16:03:29
Judged By
Score
70
Total Time
≥1599ms
Peak Memory
≥2.27 MiB