/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 576.0 KiB
#3 Accepted 33ms 788.0 KiB
#4 Accepted 37ms 788.0 KiB
#5 Accepted 44ms 856.0 KiB
#6 Accepted 42ms 788.0 KiB
#7 Accepted 51ms 1.914 MiB
#8 Accepted 51ms 1.82 MiB
#9 Accepted 50ms 1.77 MiB
#10 Accepted 74ms 13.52 MiB
#11 Accepted 86ms 13.566 MiB
#12 Accepted 75ms 13.508 MiB
#13 Accepted 54ms 1.84 MiB
#14 Accepted 50ms 1.77 MiB
#15 Accepted 63ms 832.0 KiB
#16 Accepted 56ms 880.0 KiB
#17 Accepted 37ms 788.0 KiB
#18 Accepted 39ms 832.0 KiB
#19 Accepted 41ms 984.0 KiB
#20 Accepted 79ms 1.77 MiB
#21 Accepted 77ms 13.52 MiB
#22 Accepted 83ms 13.52 MiB
#23 Accepted 78ms 13.645 MiB
#24 Accepted 77ms 13.52 MiB
#25 Accepted 77ms 13.512 MiB
#26 Accepted 59ms 836.0 KiB
#27 Accepted 146ms 14.023 MiB

Code

#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
#define int long long
#define cinv(v) for (auto &it:v) cin>>it;
#define coutv(v) for (auto &it:v) cout<< it<<' '; cout<<'\n';

const int N = 1e5 + 5, K = 20;
int n, q, x, arr[N], st[K + 1][N];

void build() {
    copy(arr, arr + n + 1, st[0]);
    int k = __lg(n);
    for (int i = 1; i <= k; ++i) for (int j = 0; j + (1 << i) <= n; ++j) st[i][j] = (st[i - 1][j] * st[i - 1][j + (1 << (i - 1))]) % x;
}

int query(int L, int R) {
    int ret = 1;
    for (int i = K; i >= 0; --i) {
        if ((1 << i) <= R - L + 1) {
            ret = (ret * st[i][L]) % x;
            L += 1 << i;
        }
    }
    return ret;
}

void shelby() {
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    build();
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        debug(l, r);
        if (query(l, r)) cout << "No\n";
        else cout << "Yes\n";
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case " << _ << ": ";
        shelby();
    }
}

Information

Submit By
Type
Submission
Problem
P1128 Roy and Product
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 17:14:29
Judged At
2024-11-05 17:14:29
Judged By
Score
100
Total Time
146ms
Peak Memory
14.023 MiB