【CF1207F】Remainder Problem

忘是亡心i 2023-06-05 08:54 79阅读 0赞

# Description #

[【CF1207F】Remainder Problem][CF1207F_Remainder Problem]

给定一个序列，支持如下操作：

*  将$x$位置的值加上$y$
 *  求出$\\sum\\limits\_\{i\\ mod\\ x= y\}\{a\_i\}$的值

# Solution #

类似于分块的思路

可以肯定，$O(n^2)$肯定是T飞了

我们假设以T为界，预处理出模数小于T的答案，查询时如果模数小于T就直接返回，时间复杂度为$O(T)$

如果模数大于T就暴力计算，时间复杂度为$O(N/T)$

显然，当$T=\\sqrt\{N\}$时这两个复杂度相等。

所以总的复杂度为$O(m\\sqrt\{N\})$

# Code #

#include <bits/stdc++.h>
    namespace shl {
        typedef long long ll;
        const int N = 5e5 + 10;
        int a[N], ans[800][800];
        int n, m;
        inline int read() {
            int ret = 0, op = 1;
            char c = getchar();
            while (!isdigit(c)) {
                if (c == '-') op = -1; 
                c = getchar();
            }
            while (isdigit(c)) {
                ret = (ret << 3) + (ret << 1) + c - '0';
                c = getchar();
            }
            return ret * op;
        }
        int main() {
            n = 500000;
            m = read();
            int size = sqrt(n);
            while (m--) {
                int op; int x, y;
                std :: cin >> op; x = read(), y = read();
                if (op == 2) {
                    if (x <= size) printf("%d\n", ans[x][y]);
                    else {
                        int sum = 0;
                        for (register int i = y; i <= n; i += x) sum += a[i];
                        printf("%d\n", sum);
                    }
                }
                else {
                    for (register int i = 1; i <= size; ++i) ans[i][x % i] += y;
                    a[x] += y; 
                }    
            }
            return 0;
        }
    }
    int main() {
        shl :: main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11403754.html

[CF1207F_Remainder Problem]: https://codeforces.com/problemset/problem/1207/F