6
22
2015
6

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: 2454
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:我数学太弱了

Avatar_small
Junior Dakil Result 说:
2022年8月31日 15:03

The Rajshahi Board is also completed the Junior School Certificate and Junior Dakil (Grade-8) terminal exams successfully under Secondary and Higher Secondary Education Board, and a huge number of students have appeared from all districts of Rajshahi Division, and those subject wise exams are completed between 1st to 3rd weeks at all schools across the country along with the divisional schools to the academic year of 2022. Both of JSC & JDC students are waiting to check their exam result with full marksheet in student wise to get total GPA grade for this year terminal exams, Junior Dakil Result rajshahi Board Grade 8th standard is the most important examination for secondary education in the country and this is gateway to secondary education in the country, and the school education department will announce student wise result with total marksheet online and this year also published same like as previous years.


登录 *


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