CF1553F Pairwise Modulo

分两种情况讨论

1. \(a_i\bmod a_j\)

• \(a_i < a_j\)

那么 \(a_j\) 对答案的贡献是 \(a_i\)。

• \(a_i > a_j\)

那么 \(a_j\) 对答案的贡献是 \(a_i-a_j \times \lfloor \dfrac{a_i}{a_j} \rfloor\)，和第一个合并一下就是 \(a_i \times (i-1) - \lfloor \dfrac{a_i}{a_j} \rfloor\)。

后面的这部分可以转化为枚举一个 \(l\)，在区间 \([a_j \times l,a_j \times (l+1) -1]\) 上加上 \(a_j \times l\)，这个可以用树状数组维护。

2. \(a_j \bmod a_i\)

• \(a_j

贡献为 \(a_j\)。

• \(a_j>a_i\)

贡献为 \(a_j-a_i \times \lfloor \dfrac{a_j}{a_i} \rfloor\)，和第一种情况同理，前面一部分贡献为 \(\sum a_j\)，后面同上一种情况，对于区间 \([a_i \times l,a_i \times (l+1) -1]\) 上减去上 \(a_j\) 在这个区间里的个数乘上 \(a_j \times l\)，同样可以用树状数组维护。

时间复杂度为 \(O(n \log^2 n)\)。

#include 
#define reg register
#define fi first
#define se second
#define mp std::make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll rd()
{
    reg ll x=0,f=0;
    reg char ch=getchar();
    while(!isdigit(ch)) (ch=='-')&&(f=1),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
#define int long long
const int MAXN=2e5+10;
const int MAXM=3e5+10;
int n,a[MAXN];
int c[MAXM][2];
// 0:val 1:num
void add(reg int x,reg int v,reg int op)
{
    for(;x