专栏文章

题解：P9148 除法题

llinjinkun
P9148题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjr5u7
此快照首次捕获于
2025/12/02 03:33
3 个月前
此快照最后确认于
2025/12/02 03:33
3 个月前
查看原文
很显然题目的数据范围 n≤5×103n \le 5 \times 10^3，复杂度显然是 O(n2)O(n^2) 或者 O(n2log⁡n)O(n^2 \log n)，很显然这题是数学题，时限又如此之大，很明显能猜出复杂度为 O(n2log⁡n)O(n^2 \log n) 级别，而说到 log⁡\log 在数学中很容易想到调和级数，那么这题就很显然了，题目要求的东西是： ∑a∈A∑b∈A∑c∈A⌊ab⌋⌊ac⌋⌊bc⌋\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>ca>b>c 的时候有贡献，那么考虑枚举枚举 b,cb,c，复杂度 O(n2)O(n^2)，然后充分利用调和级数，枚举 ss 表示 ⌊ac⌋\lfloor\frac{a}{c}\rfloor 那么 aa 能取的合法值就是一个区间，记这个区间为 [l,r][l,r]，假设能 O(1)O(1) 计算 [l,r][l,r] 的值域中 ⌊ab⌋\lfloor\frac{a}{b}\rfloor 的和，那么迎刃而解，复杂度为 O(n2log⁡n)O(n^2 \log n)，然而 O(1)O(1) 处理这个区间的贡献很容易，前缀和预处理即可。
那么最后要求的其实就是： ∑b∈A∑c∈A⌊bc⌋∑s=1maxi=1nAics∑a∈A,l≤a≤r⌊ab⌋\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 ll 和 rr 的赋值写不下了，放这里： l=max⁡(b+1,s×c)l = \max(b+1,s \times c) r=min⁡(max⁡i=1nAi,(s+1)×c−1)r = \min(\max_{i = 1}^n A_i,(s+1) \times c-1) 然后还要注意三点：
  • 首先 ll 和 rr 是值域，而并非下标，而前缀和很明显不能太方便地维护值域，所以要将 l,rl,r 转化成下标（最好预处理解决）。
  • 在算出 ll 的时候记得特判一下 l>max⁡i=1nAil>\max_{i = 1}^nA_i 的情况和换算成下标后的 l′>r′l'>r' 的可能性（我也不确定第二个要不要判，但判一下总没错，并且第一个是一定要判的）。
  • l,rl,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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...