Educational Codeforces Round 71 (Rated for Div. 2) B. Remainder Problem

题目大意

现有一个长度为 500000 500000 500000的数组 a 1 , a 2 , ⋯   , a 500000 a_1,a_2,\cdots,a_{500000} a1​,a2​,⋯,a500000​

最开始的时候，其全部为0。

现在一次进行 q q q次操作，有两种操作：

• a x = a x + y a_x=a_x+y ax​=ax​+y
• 询问 ∑ i i % x = y \displaystyle\sum_i ^ { i \%x = y} i∑i%x=y​

时间限制

4s

数据范围

q ≤ 500000 q\le 500000 q≤500000

题解

看到这个时间限制与数据范围，不免就会想到 O ( n n ) O(n\sqrt n) O(nn

​)的做法。

于是，分情况讨论：

1. 询问 x ≥ 500000 x \ge \sqrt {500000} x≥500000

   ​

   此时需要计算的数量就是 500000 n ≤ 500000 \frac{500000}{n} \le \sqrt {500000} n500000​≤500000

   ​，直接暴力计算

2. 询问 x < 500000 x < \sqrt {500000} x<500000

   ​

   此时需要计算的数就非常多了，不能暴力计算。

   但是我们发现，其余数的情况是非常有限的，于是可以预处理得出结果。

   用 s i , j s_{i,j} si,j​表示用 i i i取模后的余数是 j j j的答案，在每次修改操作的时候处理一下就可。

Code

//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#define G getchar
#define ll long long
using namespace std;

int read()
{
    char ch;
    for(ch = G();(ch < '0' || ch > '9') && ch != '-';ch = G());
    int n = 0 , w;
    if (ch == '-')
    {
        w = -1;
        ch = G();
    } else w = 1;
    for(;'0' <= ch && ch <= '9';ch = G())n = (n<<1)+(n<<3)+ch-48;
    return n * w;
}

const int N = 500005;

int n , m , x , y , t;
int s[N] , S[710][710] , ans;

int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);

    n = read();
    m = 707;

    for (int i = 0 ; i < n ; i ++)
    {
        t = read();
        x = read();
        y = read();
        if (t == 1)
        {
            s[x] += y;
            for (int j = 1 ; j <= m ; j++)
                S[j][x % j] += y;
        }
        else
        {
            ans = 0;
            if (x > m)
            {
                for (int j = 0 ; j * x + y < 500001 ; j++)
                    ans = ans + s[j * x + y];
            }
            else ans = S[x][y];
            printf("%d\n", ans);
        }
    }

    return 0;
}