bzoj 2005: [Noi2010]能量采集 容斥原理

我们先得出一个显然的结论,一个点被遮挡的掉的能量是(gcd(i,j)  – 1) * 2 + 1。

这个非常显然,自己理解。

我们考虑用g[i] 表示 gcd为i的对数。然而我们发现直接求不太容易,我们考虑容斥原理。用f[i] 表示 因数为i的对数。我们考虑g[i] = f[i] – sum(g[i * k](i * k <= min(n,m))) 。我这样子我们可以进行递推求解了。

发表评论