【HDU4944】FSF’s game


题意

求 \(\sum _{i=1}^n\sum_{j=i}^n\sum_{d|i,j}\frac{ij}{gcd(\frac{i}{d},\frac{j}{d})}\) 。

分析

因为 \(gcd(\frac{i}{d},\frac{j}{d})=\frac{gcd(i,j)}{d}\) 所以有

\(\sum _{i=1}^n\sum_{j=i}^n\sum_{d|i,j}\frac{ij}{gcd(\frac{i}{d},\frac{j}{d})}\\=\sum _{i=1}^n\sum_{j=i}^n\sum_{d|gcd(i,j)}\frac{ijd}{gcd(i,j)}\)

显然 \(\frac{ij}{gcd(i,j)}=lcm(i,j)\) ,于是 \(\sum _{i=1}^n\sum_{j=i}^n\sum_{d|gcd(i,j)}\frac{ijd}{gcd(i,j)}\\=\sum _{i=1}^n\sum_{j=i}^n\sum_{d|gcd(i,j)}lcm(i,j)d\\=\sum_{d=1}^n\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=i}^{\left \lfloor \frac{n}{d} \right \rfloor} lcm(id,jd)d\\=\sum_{d=1}^n d^2 \sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=i}^{\left \lfloor \frac{n}{d} \right \rfloor} lcm(i,j)\)。

【SPOJ】LCM Sum

解决了 \(\sum_{i=1}^n lcm(i,n)\) 这个问题,我们不妨设式子的后半部分为 \(f(\left \lfloor \frac{n}{d} \right \rfloor)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=i}^{\left \lfloor \frac{n}{d} \right \rfloor} lcm(i,j)\) 。这部分其实就是在此基础上再前缀和,有了上一题,可以很容易解决。

于是现在就是求 \(\sum_{d=1}^n d^2 f(\left \lfloor \frac{n}{d} \right \rfloor)\) ,显然 \(\left \lfloor \frac{n}{d} \right \rfloor\) 取值是 \(\sqrt{n}\) 级别的,可以数论分块,于是我们可以有 \(O(nlogn+T\sqrt{n})\) 的做法。

Tle 了两发。过不去。只能考虑优化。

我们考虑枚举 \(d\) ,然后计算 \(d\) 的贡献。

假设当前 \(\left \lfloor \frac{n}{d} \right \rfloor = i\) ,那么当前的 \(d\) 的贡献区间是 \([id,(i+1)d)\) ,且贡献为 \(d^2f(i)\) 。

可以考虑在前后打上标记,然后前缀和预处理计算。

此时复杂度变成了 \(O(\sum_{d=1}^n\left \lfloor \frac{n}{d} \right \rfloor)\) 大概近似于 \(O(nlogn)\) 就可以过了。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 67,589

Categories

Archive

Comments