在比赛的时候,被这个题目虐死了,这一周中每当我有空闲时间我就总是思索这个题目的解题方法。

终于在自己学过了mobius反演,并且看过别人写得解题思路后自己有了思路。

下面说说我的解题思路吧。

首先题目的意思很简单,给你n,m,p,问你能取出多少组有序对(x,y),使得gcd(x,y)的质因子的个数不超过p个(4看成有两个质因子)。

首先声明这个题目是mobius反演的内容。不会的先学会了再看下面的内容。

其实最先想到的肯定是和其他gcd统计问题差不多的思路啊,那就是先求mobius函数值,在求出它的和函数,在求答案的时候进行分块求解就OK了。总的时间复杂度是(n*log(n)+t*(sqrt(n)+sqrt(m)))),前面的时间是预处理的时间,显然不会超时,后面的是对每组进行求解的时间,由于进行了分块处理,所以时间复杂度降低到了log级别。(这个log级别可以这样理解:对于n不同的商其实最多只有sqrt(n)种)——不知道这样解释对不对哦。

下面就说说这个题目的特殊性吧,以前我们遇到的题目都是要你统计gcd为某一特定的数,或者为质数的值(比如说我上次发的那个PGCD),但是这个题目需要你求的是质因子数目不超过p个的数量,但是细细想来,发现其实大同小异(因为求质数相当于p==1)

下面就说说我的解题方法吧,首先声明方法是有参考自网上的神牛哦。

由于对于小于500000的数中,因子数最多的也只有18个,所以我们需要构造18个mobius函数,分别统计对应的不同的质因子数目的mobius函数值。

然后就是把函数值进行两次求和啦。

但是关键问题是怎么求出来mobius函数值呢?  这样是这个题目的关键解题方法所在。

其实我开始也不懂这个题目应该怎么做的,但是我看到有神牛的博客,忽然好想明白了一点什么。

首先在说这个问题之前,我想先说说上次我写过的那个PGCD。那个题目是要求gcd为质数的对数,我们的做法是枚举每一个数,看看它里面含有多少个不同的质因子,并且能由那些质数乘以另外一个数得到。上次说的是如果p=a*b,a,b为不同的质数,那么我们所取得那个质数可以是a,b中的任意一个,所以理论上来说有两种取法,取完之后,它本身还有一个质因子,所以它所对应的mobius函数值应该为负数。,就是这样判断出来的,如果p里面含有一个平方项的话,取出来的必定是那个平方项,于是只有一种取法,正负再由取完之后的那个数的不同的质因子数来决定。

回来看这个题目,如果我们已知某一个数还有A个不同的质因子数目,相同的质因子数目为B(2*2*2被视为2个相同的质因子数,2*2*3*3也被视为2对),显然,这个数所能够影响的mobius函数值为A-A+B(这里一定要搞清楚),同时它的影响系数为C(A,j-B)(j为mobius函数标号)(B即重复的因子一定要全部拿出来,否则函数值就为0,无影响)。

这样题目基本就被解决了,我也不想写了,今天被虐惨了,洗洗睡吧。晚安。

这个代码就不上了,自己写吧。

05-11 19:58