10.20題目龜速填坑

10/22/2015

题目链接:天下無敵金大爺的熱身題

私密比赛不给看(。题目会发上来的!

密碼是233333


 

POJ4028:GCD Guessing Game

似乎POJ的题面挂了,可以到CF的GYM上找到(。

将质因子分为乘积<=n的k组,贪心地使k最小,k即为答案。

证明大概就是,我们设ans(i)为n=i时的答案,不难证明 ans(n)<=ans(n/i)+pre[i];  i为质数i在其中的组数。


 

POJ1257:余数之和

题意:对于给定的nk,求\sum_{i=1}^{n}{k\ mod\ i}

 

考你做没做过数学题,根据(n/i)向下取整的性质,sqrt(n)分组出解。

\sum_{i=1}^{n}{k\ mod\ i}=\sum_{i=1}^{n}{k-i*\frac{k}{i}}

很显然,\frac{k}{i}只有\sqrt{k}个取值,因此我们便可以按照\frac{k}{i}来分组求和。


 

POJ2480:Longge's Problem

题意:求\sum_{i=1}^{n}gcd(i,n),(n<=2^{31})

 

首先显然原式可以化简为 \sum_{d|n}{d*\varphi(\frac{n}{d})}

我们就可以O(\sqrt{n})的复杂度枚举所有n的约数来计算惹。

还有一个小问题,就是对于很大的欧拉函数我们难以快速地计算出来。我的做法是小的phi筛出来,大的phi分解质因数来计算。(数据组数大概不是很多啦。。>_<就通过惹)。

一个比较标准的思路是,我们不难发现 \sum_{d|n}{d*\varphi(\frac{n}{d})}f(n)=ng(n)=\varphi(n)的狄利克雷卷积,而两个积性函数的狄利克雷卷积仍旧是积性函数。(关于狄利克雷卷积)

因此我们所求的\sum_{d|n}{d*\varphi(\frac{n}{d})}也就是一个积性函数,很容易每次以分解质因子的复杂度来计算它了。


SPOJ LAMSUM:

题意:求\sum_{i=1}^{n}LCM(i,n),(n<=10^{6}),共300000组询问。

 

先化简成我们比较熟悉的形式……\sum_{i=1}^{n}\frac{in}{gcd(i,n)}

交换求和次序得到    n*\sum_{d|n}\sum_{gcd(k,\frac{n}{d})=1}k

不难发现(\sum_{gcd(i,n)=1}i)=(\frac{n*\varphi(n)}{2})

因此原式可化简为   n*\sum_{d|n}\frac{d*\varphi(d)}{2}

就又可以愉快地筛出答案了!QQ图片20140806234821


SPOJ GCDEX:

题意:求\sum_{i=1}^{n}\sum_{j=i+1}^{n}gcd(i,j),(n<=10^{6}),共20000组询问。

 

我们先让这个式子在主观上变得好看一点 \sum_{i=1}^{n}\sum_{j=1}^{i-1}gcd(i,j)

那么实际上我们只需需要维护\sum_{i=1}^{n}gcd(i,n)的前缀和就好了。

显然我们发现……这个式子和我们刚刚做过的POJ2480是一样的,可以化简为\sum_{d|n}{d*\varphi(\frac{n}{d})}

只需要在筛法的时候顺便记录一下每个数最小的质因子出现过几次……即可O(n)的复杂度筛出来。

然后注意一下对于每个上限ngcd(n,n)是不应该被统计进去的,于是我们将每一个答案都减掉gcd(n,n),再统计一下前缀和,即可。


 

SPOJ PGCD:

题意:求对于所有质数p,\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=p]

 

方便起见,我们设n<=m.

一个显然的、先枚举质数(以下关于该题目的讨论中字母p均为质数)再做莫比乌斯反演的思路是将柿子(?)化简为\sum_{p}\sum_{d=1}^{\frac{n}{d}}\mu(d)\frac{n}{pd}\frac{m}{pd}

这样子。。我们每次询问的复杂度依赖于n以内质数的个数,在询问组数太多的时候会美酒药丸。

我们会很自然(大概)地想到要让讨厌的pd消失掉,不妨设s=pd

于是得到\sum_{s=1}^{n}\frac{n}{s}\frac{m}{s}\sum_{p|s}\mu(\frac{s}{p})

所以发现,我们算法的瓶颈就是对于每个S求f(s)=\sum_{p}\mu(\frac{s}{p})

略微撕烤一下\mu函数的性质,我们不难得到:
f(s*p') =\begin{cases}\mu(s), & \text{if $s\ mod\ p=0$} \\\mu(s)-f(s), & \text{others} \\\end{cases}

很容易线性晒出f(n),这道题目就解决啦w。


不过剩下的题稍微有些懒得更新~(