最近在其他地方写文章,为了证明我没咕,把最近写的转到 Mina 上来吧。
文章或许有纰漏,希望大神可以指出 QwQ 。那么进入正题吧。
很显然是让我们求出下式:
ans=A∑i=1B∑j=1[gcd(i,j)=K]
根据性质可以得到:
ans=⌊AK⌋∑i=1⌊BK⌋∑j=1[gcd(i,j)=1]
我们设两个函数:
- 函数 f,f(x) 表示 ∑⌊AK⌋i=1∑⌊BK⌋j=1[gcd(i,j)=x]
- 函数 g ,g(x) 表示 ∑⌊AK⌋i=1∑⌊BK⌋j=1[x|gcd(i,j)]
我们可以得到:
g(x)=∑x|df(d)
这是莫比乌斯反演的第二个形式:
g(n)=∑n|df(d) ⇒ f(n)=∑n|dg(d)⋅μ(dn)
于是:
g(x)=∑x|df(x) ⇒ f(x)=∑x|dg(x)⋅μ(dx)
=g(x)=∑x|df(x) ⇒ f(x)=∑x|dg(dx)⋅μ(x)
设 n=⌊AK⌋ , m=⌊BK⌋
那么:
g(x)=n∑i=1m∑i=1[x|gcd(i,j)]=⌊nK⌋∑i=1⌊mK⌋∑j=1[1|gcd(i,j)]
=⌊nK⌋∑i=1⌊mK⌋∑j=1[1|gcd(i,j)]=⌊AK⌋×⌊BK⌋
ans=f(1)
f(1)=n∑i=1μ(i)⋅g(i)=n∑i=1μ(i)⋅⌊AK⌋⋅⌊BK⌋
这个式子是 O(n) 的。
发现 ⌊AK⌋×⌊BK⌋ 可以整除分块,于是我们便可以做到 O(√n)
Code:
所以就没了。
0 条评论