TIOJ 2120：輸贏吧！在序列征戰中

TIOJ 2120：輸贏吧！在序列征戰中

題目大意：給你一個長度為 $N$ 的數列 $A_1\sim A_n$，$Q$ 筆詢問，兩個數字 $C, P$。每次詢問可能有三種形式，第一種請你將 $l\leq i \leq r$ 的 $A_i$ 變成 $C^{A_i}$，第二種請你輸出 $\sum\limits_{i = l}^r A_i\ (\text{mod}\ P)$，第三種請你將 $A_p$ 變成 $v$。

解法：如果我們要計算 $a^x\ (\text{mod}\ P)$，根據歐拉定理，當 $\gcd(a, P) = 1$ 時，$a^x \equiv a^{x\ (\text{mod}\ \varphi(P))} \equiv a^{x\ (\text{mod}\ \varphi(P)) + \varphi(P)}\ (\text{mod}\ P)$，當 $\gcd(a, P) = g > 1$ 時，前面會有不循環的部分，而後面每 $\varphi(\frac{P}{g})$ 一個循環，因為 $\varphi(\frac{P}{g})$ 整除 $\varphi(P)$，所以 $\varphi(P)$ 也是一個循環節，而前面不循環的部分因為在 $\text{mod}\ \varphi(P)$ 下，只會有 $0\sim \varphi(P) - 1$ 共 $\varphi(P)$ 個數字，所以最多只會有 $\varphi(P)$ 個不循環的數字，那當 $x<\varphi(P)$ 時，$a^x$ 可以直接算，當 $x\geq\varphi(P)$ 時，$a^x\equiv a^{x\ (\text{mod}\ \varphi(P)) + \varphi(P)}\ (\text{mod}\ P)$。

因為 $\varphi(\varphi(P)) \leq \frac{P}{2}$，所以最多只會遞迴 $\log(P)$ 次，那我們就可以用一個 $\text{set}$ 記錄有哪些數字還沒遞迴到 $\log(P)$ 次，如果到了，那 $C^{A_i} \equiv A_i\ (\text{mod}\ P)$，就可以從 $\text{set}$ 刪掉，因為 $Q≒N$，所以最後的複雜度大概就是 $O(N\times(\log(N) + \log^2(P)))$。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, q, c;
set<int> s;
int len, ph[16];
int a[SIZE], val[SIZE], cnt[SIZE], bit[SIZE];

void update (int pos, int x) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += x;
}

int query (int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}

int Mod (int x, int mod) {
    return x < mod ? x : x % mod + mod;
}

int phi (int x) {
    int re = 1;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            re *= i - 1;
            x /= i;
            while (x % i == 0) {
                re *= i;
                x /= i;
            }
        }
    }
    if (x > 1) re *= x - 1;
    return re;
}

int power (int d, int up, int mod) {
    int ans = 1;
    while (up) {
        if (up & 1) ans = Mod (ans * d, mod);
        d = Mod (d * d, mod);
        up >>= 1;
    }
    return ans;
}

int cal (int i, int id) {
    int x = (id <= cnt[i] ? c : a[i]), mod = ph[id];
    x = Mod (x, mod);
    if (mod == 1 || id == cnt[i] + 1) return x;
    return power (x, cal (i, id + 1), mod);
}

void solve() {
    int mod, x;
    cin >> n >> q >> c >> mod;
    x = ph[++len] = mod;
    while (x > 1) x = ph[++len] = phi (x);
    FOR (i, 1, n) {
        cin >> a[i];
        s.insert (i);
        val[i] = a[i] % mod;
        update (i, val[i]);
    }
    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int l, r;
            cin >> l >> r;
            for (auto it = s.lower_bound (l); it != s.end() && *it <= r;) {
                cnt[*it]++;
                int x = cal (*it, 1) % mod;
                update (*it, x - val[*it]);
                val[*it] = x;
                if (cnt[*it] + 1 >= len) it = s.erase (it);
                else it++;
            }
        }
        if (ty == 2) {
            int l, r, x;
            cin >> l >> r;
            x = (query (r) - query (l - 1)) % mod;
            cout << (x < 0 ? x + mod : x) << '\n';
        }
        if (ty == 3) {
            int p, v;
            cin >> p >> v;
            a[p] = v;
            v %= mod;
            update (p, v - val[p]);
            val[p] = v;
            cnt[p] = 0;
            s.insert (p);
        }
    }
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！