HDU 5475.An easy problem

题目大意

一开始给你一个数n=1和一个模数M（不一定为质数），之后会有q（$q<10^5$）次操作，每次操作操作给两个数f，x（$x<10^9$）

• f=1时，表示给n乘上x
• f=2时，表示给n除以第x次操作乘的那个数

每次操作后输出n对M取模的值。

分析

因为M不为质数，所以显然不能用逆元。x也很大，高精很有可能被卡时间复杂度。此时不难想到万能数据结构——分块。

具体做法是，将每次乘的数放到一个块里，然后对于每个块维护乘数模M的结果ans[i]。当f=1时，将x插入到相应的块中，同时将ans[i]乘上x再取模。当f=2时，将块中的x直接修改为1，并暴力重构块。

每次操作后n的值就是ans[]的积。

当然线段树也是可以的。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

struct opt {
    int f, x;
}o[N];

int block[1000 + 5][2000 + 5], p[1000 + 5], ans[1000 + 5];
int arr[N];
int n, q, m, lenBlock;

int id(int x) {
    return lower_bound(arr, arr + q, x) - arr;
}

void build() {
    memset(p, 0, sizeof p);
    for (int i = 0; i < n; i++) ans[i] = 1;
}

void process(int x) {
    ans[x] = 1;
    for (int i = 0; i < p[x]; i++) ans[x] = ans[x] * 1ll * block[x][i] % m;
}

int getAns() {
    int res = 1;
    for (int i = 0; i < n; i++) res = res * 1ll * ans[i] % m;
    return res;
}

void add(int x) {
    int pos = id(x), i = pos / lenBlock;
    block[i][p[i]++] = x;
    ans[i] = ans[i] * 1ll * x % m;
}

void del(int x) {
    int pos = id(x), i = pos / lenBlock;
    for (int j = 0; j < p[i]; j++) if (block[i][j] == x){
        block[i][j] = 1;
        break;
    }
    process(i);
}


int main() {
    int T; cin >> T;
    for (int kase = 1; kase <= T; kase++) {
        cin >> q >> m;
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &o[i].f, &o[i].x);
            arr[i] = o[i].x;
        }
        sort(arr, arr + q);
        lenBlock = sqrt(q + 0.5);
        n = ceil((q + 0.0) / lenBlock);
        build();
        printf("Case #%d:\n", kase);
        int res = 1;
        for (int i = 0; i < q; i++) {
            if (o[i].f == 1) add(o[i].x), res = res * 1ll * o[i].x % m;
            else del(o[o[i].x - 1].x), res = getAns();
            printf("%d\n", res);
        }
    }
}