Pairwise Modulo

题面

给定一个由不同数组成的序列 $a$ ，定义 $p_k$ 为：

$$p_k = \sum_{i=1}^k \sum_{j=1}^k a_i \bmod a_j $$

其中 $a_i \bmod a_j$ 表示 $a_i$ 除以 $a_j$ 的余数。对于每个 $i \in [1,n]$ ，求出 $p_i$ 。

$2\le n \le 2 \cdot 10^5,1 \le a_i \le 3 \cdot 10^5$ .

题解

$$p_i=p_{i-1}+\sum_{j=1}^{i-1}a_i\bmod a_j+\sum_{j=1}^{i-1}a_j\bmod a_i $$

开两个树状数组存位置和值即可。

代码

const int N = 2e5 + 5, M = 3e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n, ans, sum;
	struct BIT {
		ll t[M];
		void modify (ll x, ll val) { for (; x < M; x += x & -x) t[x] += val;}
		ll query (ll x) { ll ans = 0; for (; x; x -= x & -x) ans += t[x]; return ans;}
	} t1, t2;
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) {
			ll a = Read();
			ans += sum + (i - 1) * a - t1.query(a);
			for (ll j = a; j < M; j += a) {
				int blk = min (M - 1ll, j + a - 1);
				ans -= j * (t2.query(blk) - t2.query(j - 1));
				t1.modify(j, j), t1.modify(blk + 1, -j);
			}
			t2.modify(a, 1);
			sum += a;
			printf ("%lld ", ans);
		}
		
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}