/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 332.0 KiB
#2 Accepted 2ms 328.0 KiB
#3 Accepted 146ms 868.0 KiB
#4 Accepted 146ms 836.0 KiB
#5 Accepted 149ms 900.0 KiB
#6 Accepted 189ms 796.0 KiB
#7 Accepted 188ms 1.023 MiB
#8 Accepted 203ms 1.074 MiB
#9 Accepted 212ms 1.07 MiB
#10 Accepted 218ms 2.273 MiB
#11 Accepted 194ms 1.605 MiB
#12 Accepted 227ms 1.832 MiB
#13 Accepted 220ms 1.102 MiB
#14 Accepted 145ms 1.016 MiB
#15 Accepted 264ms 852.0 KiB
#16 Accepted 277ms 796.0 KiB
#17 Accepted 221ms 896.0 KiB
#18 Time Exceeded ≥1553ms ≥720.0 KiB
#19 Time Exceeded ≥1597ms ≥752.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-11 02:28:42
Judged By
Score
70
Total Time
≥1597ms
Peak Memory
≥2.273 MiB