把所有相同取值聚合。设 U=max(ai)U=\max(a_i)U=max(ai)，定义频次数组 cnt[x]cnt[x]cnt[x] 表示值为 xxx 的元素个数。则
SSS=∑y=1Ucnt[y]⋅H(y)\sum_{y=1}^{U} cnt[y]\cdot H(y)∑y=1Ucnt[y]⋅H(y),\quad
H(y)H(y)H(y)=∑x=1Ucnt[x]\sum_{x=1}^{U} cnt[x]∑x=1Ucnt[x] ⋅⌊xy⌋.\cdot \left\lfloor \dfrac{x}{y}\right\rfloor.⋅⌊yx⌋.
对固定的 yyy，当 x∈[ky,(k+1)y−1]x\in [ky,(k+1)y-1]x∈[ky,(k+1)y−1] 时有 ⌊xy⌋\left\lfloor \dfrac{x}{y}\right\rfloor⌊yx⌋=kkk。因此可以把 [1,U][1,U][1,U] 按长度为 yyy 的区间分块：
给定nnn个元素aia_iai，要求计算以下表达式的值:
S=∑1≤i≤n∑1≤j≤n⌊aiaj⌋S=\sum_{1 \leq i \leq n} \sum_{1 \leq j \leq n}\left\lfloor\frac{a_{i}}{a_{j}}\right\rfloorS=∑1≤i≤n∑1≤j≤n⌊ajai⌋
本题属于以下题库，请选择所需题库进行购买
ScanQRCodePrompt
请使用微信扫描下方二维码完成注册
