CF1207F Remainder Problem

/px

被卡读入，自毙。

按照下标分块，令块大小为$N$，则对于每一组询问$(x,y)$，当$x\geq N$时直接暴力枚举所有符合要求的点$xk+y$（不会超过$N$个）；

对于$x<N$的情况，我们维护一个二维数组$arr[x][y]$，表示$arr[x][y]$的答案，回答时直接输出即可。

对于修改操作，我们直接枚举所有不超过$N$的数，分别取模后修改数组即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;
using pair_t = std::pair<int_t, int_t>;
const int_t mod = 998244352;
int_t power(int_t base, int_t index) {
    const int_t phi = mod - 1;
    index = (index % phi + phi) % phi;
    int_t result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}

const int_t LARGE = 5e5;
const int_t SQRT = 700;
int_t n, m;
int_t arr[LARGE + 1];
int_t vecs[SQRT + 1][SQRT + 1];
template <class T>
void read(T& x) {
    x = 0;
    T flag = 1;

    char chr = getchar();
    while (chr != '-' && isdigit(chr) == false) chr = getchar();
    if (chr == '-') flag = -1;
    while (isdigit(chr) == false) chr = getchar();
    while (isdigit(chr)) {
        x = x * 10 + chr - '0';
        chr = getchar();
    }
    x *= flag;
}
template <class T>
void write(T x) {
    if (x < 0) {
        x *= -1;
        putchar('-');
    }
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
int main() {
    std::ios::sync_with_stdio(false);
    int_t q;
    // cin >> q;
    read(q);

    while (q--) {
        int t, x, y;
        read(t);
        read(x);
        read(y);
        // cin >> t >> x >> y;
        // scanf("%d%d%d", &t, &x, &y);
        if (t == 1) {
            arr[x] += y;
            for (int_t i = 1; i <= SQRT; i++) vecs[i][x % i] += y;
        } else {
            if (x <= SQRT) {
                // printf("%d\n", (int)vecs[x][y]);
                // cout << (int)vecs[x][y] << endl;
                write((int)vecs[x][y]);
                putchar('\n');
            } else {
                int_t result = 0;
                for (int_t i = 0; i * x + y <= LARGE; i++) {
                    result += arr[i * x + y];
                }
                // printf("%d\n", int(result));
                // cout << int(result) << endl;
                write(int(result));
                putchar('\n');
            }
        }
    }
    return 0;
}