题解：P9148 除法题
linjinkun
·
·
题解
很显然题目的数据范围 n \le 5 \times 10^3，复杂度显然是 O(n^2) 或者 O(n^2 \log n)，很显然这题是数学题，时限又如此之大，很明显能猜出复杂度为 O(n^2 \log n) 级别，而说到 \log 在数学中很容易想到调和级数，那么这题就很显然了，题目要求的东西是：
\sum_{a \in A}\sum_{b \in A}\sum_{c \in A}\lfloor \frac{a}{b}\rfloor\lfloor \frac{a}{c}\rfloor\lfloor \frac{b}{c}\rfloor
很显然只有在 a>b>c 的时候有贡献，那么考虑枚举枚举 b,c，复杂度 O(n^2)，然后充分利用调和级数，枚举 s 表示 \lfloor\frac{a}{c}\rfloor 那么 a 能取的合法值就是一个区间，记这个区间为 [l,r]，假设能 O(1) 计算 [l,r] 的值域中 \lfloor\frac{a}{b}\rfloor 的和，那么迎刃而解，复杂度为 O(n^2 \log n)，然而 O(1) 处理这个区间的贡献很容易，前缀和预处理即可。
那么最后要求的其实就是：
\sum_{b \in A}\sum_{c \in A}\lfloor\frac{b}{c}\rfloor\sum_{s = 1}^{\frac{max_{i = 1}^n A_i}{c}}s\sum_{a \in A,l \le a \le r}\lfloor\frac{a}{b}\rfloor
$$l = \max(b+1,s \times c)$$
$$r = \min(\max_{i = 1}^n A_i,(s+1) \times c-1)$$
然后还要注意三点：
- 首先 $l$ 和 $r$ 是值域，而并非下标，而前缀和很明显不能太方便地维护值域，所以要将 $l,r$ 转化成下标（最好预处理解决）。
- 在算出 $l$ 的时候记得特判一下 $l>\max_{i = 1}^nA_i$ 的情况和换算成下标后的 $l'>r'$ 的可能性（我也不确定第二个要不要判，但判一下总没错，并且第一个是一定要判的）。
- $l,r$ 的转下标方式不一样，一个是 `lower_bound`，一个是 `upper_bound`。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
const long long mod = 1ll<<32;
int b[N],pre[N][N],c[N],a[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,maxx = 0;
cin >> n;
for(int i = 1;i<=n;++i)
{
cin >> a[i];
maxx = max(maxx,a[i]);
}
sort(a+1,a+n+1);
for(int i = 1;i<=n;++i)
{
for(int j = 1;j<=maxx;++j)
{
pre[i][j] = pre[i-1][j]+a[i]/j;
}
}
for(int i = 1;i<=maxx;++i)
{
b[i] = lower_bound(a+1,a+n+1,i)-a;
c[i] = upper_bound(a+1,a+n+1,i)-a-1;
}
long long ans = 0;
for(int i = 1;i<=n;++i)
{
for(int j = 1;j<i;++j)
{
int cc = a[i]/a[j];
int MAX = maxx/a[j];
long long sum = 0;
for(int k = 1;k<=MAX;++k)
{
int ll = max(a[i]+1,k*a[j]),rr = min(maxx,(k+1)*a[j]-1);
if(ll>maxx)
{
continue;
}
int l = b[ll],r = c[rr];
if(l>r)
{
continue;
}
sum = (sum+k*(pre[r][a[i]]-pre[l-1][a[i]])%mod)%mod;
}
ans = (ans+cc*sum%mod)%mod;
}
}
cout << ans;
return 0;
}
```