Educational Codeforces Round 71 (Rated for Div. 2) F.Remainder Problem(分块暴力)

题目链接
思路：
设 $f\left[i\right]\left[j\right]$f[i][j]为范围在1-800内 模i为j的所有答案
然后对每个修改操作直接改，然后如果x<=800的话直接更新一下f。

对于每个询问操作，小范围直接输出f[x][y]，大范围直接暴力即可
因为每次操作处理最多是800的
所以复杂度可以保证

#include<bits/stdc++.h>
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define ALL(X) X.begin(),X.end()
 
using namespace std;
 
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e6 + 11;
int q;
LL a[N], b[N], f[877][877];
int main() {
	ios::sync_with_stdio(false);
	for (cin >> q; q; q--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1) {
			b[x] += y;
			for (int i = 1; i <= 800; i++) {
				f[i][x % i] += y;
			}
		} else {
			LL ans = 0;
			if (x <= 800 )
				ans += f[x][y];
			if (x > 800)
				for (int j = y; j <= 500000; j += x) {
					ans += b[j];
				}
			cout << ans << endl;
		}
	}
	return 0;
}