[BZOJ2005 [Noi2010]能量采集]【容斥定理】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2005

【题目大意】

给出m,n，求Sum{gcd(i,j) | 1<=i<=m && 1<=j<=n}*2-m*n。

【算法分析】

下面所有/都表示整除。

看了oimaster的题解，Orz容斥原理原来可以这么用= =。Orz比正解更快的解法。

我们先枚举g=gcd(i,j)。然后转化为求1<=i<=m/g && 1<=j<=n/g，并且gcd(i,j)=1的二元对(i,j)的个数。

然后我们考虑这个新的问题。

令x=m/g y=n/g

显然ans=x*y-所有gcd(i,j)>1的二元对个数。

后者res可以通过容斥原理求解。

先假设我们先把1~m的素数求了出来。存在p数组里面。

然后后者就等于f(p[1])∪f(p[2])∪f(p[3])….的个数。（其中f(t)表示t在gcd(i,j)>1里面所占的二元对。）

我们套用容斥原理的公式可以发现，1~x每个数字都最多只会被使用一次。

res=-f(1)+f(2)+f(3)+f(5)-f(6)….

若t分解质因数对于同一个素因子含有两个以上，那么不会被容斥原理所需要。

若t分解质因数有偶数个素因子，那么前面的系数为-1。

若t分解质因数有奇数个素因子，那么前面的系数为1。

、

、

、

、

回到原题。

因为a/b/c = a/(b*c)

所以我们可以直接按容斥求那个res。暴力得解。

【时间复杂度】

先预处理那个f()前面的系数n lg n即可。

后面的暴力的部分的复杂度相当于

1<=i<=n && 1<=j<=i

i%j==0的对数。

= =其实就是约数啦。。。

单个数的约数是可能到达该数的sqrt(n)级别的。

但是前n个约数的个数的和是n lg n级别的。。。

所以后面这部分的时间复杂度也是n lg n。

总的时间复杂度O(n lg n)

【CODE】

C++ CODE   :Noi2010 energy 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 #include