【HAOI2011】Problem b


题意

求 \(\sum_{i=a}^b \sum_{j=c}^d [gcd(i,j)=k]\) 。

分析

因为 \(\sum _{i=1}^n\sum_{j=1}^mf(gcd(i,j))=\sum _{T=1}^ng(T)\left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor\) ,其中\(g(T)=\sum_{d|T}f(d)\mu(\frac{T}{d})=f*\mu\) 。

我们令 \(f(k)=1,f(x)=0(x\neq k)\) 并且假设 \(n\le m\) 。

于是就有 \(\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)=k]\\=\sum _{T=1,k|T}^n\mu(\frac{T}{k})\left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor\\=\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\mu(d)\left \lfloor \frac{n}{dk} \right \rfloor \left \lfloor \frac{m}{dk} \right \rfloor\) 。

因为有多组询问,这样的时间复杂度仍然是不允许的。

我们可以考虑数论分块,所谓数论分块,无非是 \(\left \lfloor \frac{n}{dk} \right \rfloor \left \lfloor \frac{m}{dk} \right \rfloor\) 这部分的取值是 \(\sqrt{n}\) 级别的,所以我们可以考虑把相同的一起算。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,993

Categories

Archive

Comments