Pairwise Modulo
题目链接：luogu CF1553F
题目大意
给你一个序列，对于每个前缀，要你求两两互相取模的结果的和。
思路
考虑新加入一个数增加的答案。
那就是加两个部分：
\(\sum\limits_{i=1}^{n-1}a_n\% a_i\)
\(\sum\limits_{i=1}^{n-1}a_i\%a_n\)
然后分别考虑。
不过有一个通用的化法就是 \(a\%b=a-\left\lfloor\dfrac{a}{b}\right\rfloor b\)
然后：
\(\sum\limits_{i=1}^{n-1}a_n- \left\lfloor\dfrac{a_n}{a_i}\right\rfloor a_i\)
\(\sum\limits_{i=1}^{n-1}a_i- \left\lfloor\dfrac{a_i}{a_n}\right\rfloor a_n\)
\(a_n(n-1)-\sum\limits_{i=1}^{n-1}\left\lfloor\dfrac{a_n}{a_i}\right\rfloor a_i\)
\(\sum\limits_{i=1}^{n-1}a_i-\sum\limits_{i=1}^{n-1}\left\lfloor\dfrac{a_i}{a_n}\right\rfloor a_n\)
那就看怎么算两个的右边。
发现第二个是好搞的，直接枚举 \(\left\lfloor\dfrac{a_i}{a_n}\right\rfloor\) 的值，然后查询 \(a_nk\sim a_n(k+1)-1\) 里面有多少个之前的数，用树状数组维护求即可。
然后 \(\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor=n\log n\) 所以复杂度为 \(O(n\log^2n)\)
然后再看第一个，发现直接不好问，但是考虑从贡献的数的角度来看，那也看下取整的部分，它的多少倍就要让自己贡献多少次。
于是考虑每次放进去一个数 \(x\)，就把它倍数的所有位置都加上 \(x\)，然后询问的时候直接问 \(1\sim y\) 的和即可，也是树状数组维护。
然后也是枚举倍数，也是树状数组，所以也是 \(n\log^2n\) 的。
然后有一种根号分治的做法，但是复杂度会劣到 \(O(n\sqrt{n\log n})\)，但也能过。
其实两种的想法差不多，这里只说第一个。
我们设定一个阀值 \(B\)，当数 \(\leqslant B\) 的时候，我们暴力取模加入答案。
当 \(>B\)，这个时候模 \(n\) 的结果只有 \(\dfrac{n}{B}\log n\) 种（不确定是不是这个不是很会分析），我们考虑枚举这些，然后找到对应的范围，也用树状数组查询数量。
然后当 \(B=\sqrt{n\log n}\) 的时候，复杂度是 \(O(n\sqrt{n\log n})\)
代码
\(O(n\log^2n)\)
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const ll N = 3e5 + 2e5;
const ll Lim = 3e5;
ll n, a[N];
struct SZSZ {
ll f[N];
void insert(ll x, ll y) {
for (; x <= Lim; x += x & (-x))
f[x] += y;
}
ll query(ll x) {
ll re = 0; for (; x; x -= x & (-x)) re += f[x]; return re;
}
ll ask(ll l, ll r) {
return query(r) - query(l - 1);
}
}T, Ts;
ll re; char c;
ll read() {
re = 0; c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re;
}
int main() {
// freopen("read.txt", "r", stdin);
// freopen("write.txt", "w", stdout);
n = read();
for (ll i = 1; i <= n; i++) a[i] = read();
ll ans = 0, sum = 0;
for (ll i = 1; i <= n; i++) {
ans -= Ts.ask(1, a[i]);
ans += 1ll * (i - 1) * a[i];
ll tmp = Lim / a[i];
for (int j = 1; j <= tmp; j++) {
int L = j * a[i], R = min((j + 1) * a[i] - 1, Lim);
ans -= 1ll * j * a[i] * T.ask(L, R);
}
ans += sum;
T.insert(a[i], 1); sum += a[i];
for (ll j = a[i]; j <= Lim; j += a[i]) Ts.insert(j, a[i]);
printf("%lld ", ans);
}
return 0;
}
\(O(n\sqrt{n\log n})\)
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int N = 3e5 + 2e5;
const int Lim = 3e5;
int n, a[N], B;
bool in[N];
struct SZSZ0 {
int f[N];
inline void insert(int x, int y) {
for (; x <= Lim; x += x & (-x))
f[x] += y;
}
inline int query(int x) {
int re = 0; for (; x; x -= x & (-x)) re += f[x]; return re;
}
inline int ask(int l, int r) {
return query(r) - query(l - 1);
}
}T;
struct SZSZ {
ll f[N];
inline void insert(int x, int y) {
for (; x <= Lim; x += x & (-x))
f[x] += y;
}
inline ll query(int x) {
ll re = 0; for (; x; x -= x & (-x)) re += f[x]; return re;
}
inline ll ask(int l, int r) {
return query(r) - query(l - 1);
}
}Ts;
int get_log(int x) {
return x * (int)(log10(x) / log10(2));
}
int re; char c;
int read() {
re = 0; c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re;
}
void write(ll x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int main() {
// freopen("read.txt", "r", stdin);
// freopen("write.txt", "w", stdout);
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
ll ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
B = max(1, (int)sqrt(get_log(a[i])));
int L = a[i] / 2 + 1, R = a[i], tmp = a[i] / B;
for (int j = 1; j <= tmp; j++) {
// int L = a[i] / (j + 1) + 1, R = a[i] / j;
ans -= Ts.ask(L, R) * j;
if (j != tmp) R = L - 1, L = a[i] / (j + 2) + 1;
}
for (int j = 1; j <= L - 1; j++) {
if (!in[j]) continue;
// ans -= a[i] - (a[i] - a[i] / j * j);
ans -= a[i] / j * j;
}
ans += 1ll * (i - 1) * a[i];
tmp = Lim / a[i];
for (int j = 1; j <= tmp; j++) {
int L = j * a[i], R = min(Lim, (j + 1) * a[i] - 1);
ans -= 1ll * j * a[i] * T.ask(L, R);
}
ans += sum;
T.insert(a[i], 1); Ts.insert(a[i], a[i]); sum += a[i]; in[a[i]] = 1;
write(ans); putchar(' ');
// printf("%lld ", ans);
}
return 0;
}
//根号分治