6
22
2015
5

Dzy loves Math系列题解

最近发现数学非常有趣,于是决定去膜拜jc等神犇出的神题。

UPD:

2015.6.30 感觉这个坑要成无底洞了,希望能在noi前做完6题吧。

 

 

4/8

 


 

Dzy loves Math I

 

设[tex]g(x)=\sum_{d|x}f(d)\mu (\frac{x}{d})[/tex],则显然答案为[tex]\sum_{i=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{i} \right \rfloor g(i)[/tex]。如果我们预处理出[tex]g[/tex]函数的前缀和,是可以在[tex]O(\sqrt{n})[/tex]的时间内完成每次询问的。

如果[tex]x=1[/tex],那么[tex]g(x)=0[/tex];否则,设[tex]x=\prod_{i=1}^{k}p_{i}^{a_{i}}(a_{1}\leq a_{2}\leq ...\leq a_{k})[/tex],若[tex]a_{1}=a_{2}=...=a_{k}[/tex],则[tex]g(x)=\mu(\prod_{i=1}^{k} p_{i})[/tex],否则[tex]g(x)=0[/tex]。

 


 

Dzy loves Math V

 

由于[tex]\varphi [/tex]是积性函数,可以枚举每个质数分别计算对答案的贡献。考虑枚举的质数为[tex]x[/tex],对于每个数[tex]a_{i}[/tex],设[tex]k_{i}[/tex]为最大的能够满足[tex]x^k_{i}|a_{i}[/tex]的整数,那么,记[tex]P=\prod_{i=1}^{N}(\sum_{j=0}^{k_{i}}x^{j})[/tex],由欧拉函数的公式可知,[tex]x[/tex]对答案的贡献为[tex]\frac{(P-1)(x-1)}{x}+1[/tex]。实现的时候,枚举每个质数以及他们的倍数,时间复杂度为[tex]O(Alog_{2}A)[/tex],其中[tex]A[/tex]为最大的[tex]a_{i}[/tex]。

 


 

Dzy loves Math VI

 

     [tex]\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)^{gcd(i,j)}

[tex]=\sum_{i=1}^{n}\sum_{j=1}^{m}(\frac{ij}{gcd(i,j)})^{gcd(i,j)}

[tex]=\sum_{d}\sum_{i=1}^{n}\sum_{j=1}^{m}(\frac{ij}{d})^{d}[gcd(i,j)=d]

[tex]=\sum_{d}\frac{\sum_{k}\mu (k)(kd)^{2d}\sum_{i=1}^{\left \lfloor \frac{n}{kd} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{kd} \right \rfloor}i^dj^d}{d^d}[/tex]

剩下没什么好说的了。。。

 


 

Dzy loves Math VIII

 

设[tex]f(n)=\sum_{i=1}^{n}\mu(lcm(i,n)^{gcd(i,n)})[/tex],我们的目标是求出所有的[tex]f(n)[/tex]。

当[tex]gcd(i,n)>1[/tex]时,[tex]lcm(i,n)>1[/tex],则[tex]\mu(lcm(i,n)^{gcd(i,n)})=0[/tex],于是

      [tex]f(n)=\sum_{i=1}^{n}\mu(in)[gcd(i,n)=1]

[tex]=\mu(n)\sum{i=1}^{n}\mu(i)[gcd(i,n)=1]

[tex]=\mu(n)\sum_{d|n}\mu(d)\sum_{i=1}^{\frac{n}{d}}\mu(id)[/tex]

设[tex]g(n,d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\mu(id)[/tex]。

对于每一个square-free number[tex]n[/tex],我们求出[tex]n[/tex]的所有因数,这是可以在线性筛时记录最小因数搞出来的。然后我们更新一下所有的[tex]g(n,d)[/tex],并累加到[tex]f(n)[/tex]中,时间复杂度不到[tex]O(nlogn)[/tex],看吉丽的博客上写的是[tex]O(n\alpha_{n})[/tex],其中当[tex]n=10000000[/tex]时,[tex]\alpha_{n}\approx 5.468[/tex]。
Category: 题解 | Tags: | Read Count: 1226
Avatar_small
Recursion 说:
2015年6月22日 21:42

妈呀太神了Orz
感觉自己数学好弱T_T

Avatar_small
SanSiroWaltz 说:
2015年6月22日 21:57

@Recursion: 我只会做良心一点的数论题。。。碰到II和III这种题就被虐爆啦

Avatar_small
Recursion 说:
2015年6月23日 08:20

@SanSiroWaltz: 我总是觉得数论题公式推起来很蛋疼T_T

Avatar_small
bx2k 说:
2015年6月26日 13:41

@Recursion:
@SanSiroWaltz:
你们咋都这么神!

Avatar_small
Recursion 说:
2015年6月26日 15:32

@bx2k:我数学太弱了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com