公式推♂倒题

国内ICPC中经常出现的一类问题！一般会给一个复杂度炒鸡吓人的式子，然后我们需要大力推倒他。把复杂度降到Accepted的范围。

一些前置技能点总结

跳跳狗

([frac{n}{i}])可以取到的值，个数是(O(sqrt n))级别的。

int nex=1;
for(int i=1;i<=n;i=nex+1) {
	nex=n/(n/i); // 对于[i,nex]区间内所有数字x，n/x相等。
}

如果需要计算，(sum_{i=1}^{n} [frac{n}{i}])这种东西，我们就可以把([frac{n}{i}])相同的(i)，放在一起处理。

莫比乌斯函数

这个东西本身上就是容斥吖！一个经典的式子：(sum_{d|n} mu(d) = [n=1])

我们，把(n)分解质因子拆了(n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k})

我们考虑(n)的因子(d),如果(mu(d))不为0，那么每个质因子在(d)里面的指数，要么是0，要么是1.

如果(d)包含奇数个质因子，那么(mu(d)=-1), 否则(mu(d)=1).

所以(mu(d)=-1)的(d)有(C(k,1)+C(k,3)+....)个。
所以(mu(d)=+1)的(d)有(C(k,0)+C(k,2)+....)个。

根据((1-1)^k)二项式定理的展开，当(n)不为1时，(sum_{d|n} mu(d)=0)

当然这个式子是可以进化的。

我们用类似的方法，同样也可以得到(sum_{d^2|n} mu(d) = mu(n)^2)

推倒的姿势

姿势1：考虑一下公因子，质因子什么的

按因子统计的问题。出现得相当多了。

栗子1：给出(n(nleq2000000)),计算:

(sum_{i=1}^{n} sum_{j=1}^{n} gcd(i,j))

做法:

我们按照gcd分类一下可化成。(sum_{g=1}^{n}(gsum_{i=1}^{n/g}sum_{j=1}^{n/g} [gcd(i,j)=1]))

令(f(x)=sum_{i=1}^{x}sum_{j=1}^{x} [gcd(i,j)=1] = sum_{d=1}^{x} mu(d)(frac{x}{d})^2)

(f(x))可以按照(frac{x}{d})分类，使用跳跳狗来分块计算，复杂度(O(sqrt x)),原式 = (sum_{g=1}^{n} g*f(frac{n}{g}))，按照(frac{n}{g})的值使用跳跳狗分块计算即可。

栗子2: 2018沈阳网络赛C

做法:

式子可化为(sum_{i=1}^{n}sum_{j=1}^{i} j^2mu(j)^2 = sum_{i=1}^{n}sum_{j=1}^{i}j^2sum_{d^2|j}mu(d))

交换求和顺序，枚举d,式子可化为(sum_{d=1}^{sqrt n}sum_{j=1}^{frac{n}{d^2}}(n-d^2j+1)(d^2j)^2)

难看死了，整理一下(sum_{d=1}^{sqrt n}[((n+1)d^4sum_{j=1}^{frac{n}{d^2}}j^2)-(d^6sum_{j=1}^{frac{n}{d^2}}j^3)])

中括号里的那个吓死人的东西，其实可以(O(1))计算哎！于是我们就施展开了。

然后注意一下：

首先这个题要用快速乘！
然后(frac{x}{y}\%p = frac{x\%(yp)}{y}) [很好推的啦！]

栗子3: SDOI2015约数个数和

我们要求(sum_{i=1}^{n}sum_{j=1}^{m}d(ij))

按公因子分类,化为(sum_{g=1}^{n}d(g)sum_{i=1}^{n/g}sum_{j=1}^{m/g} d(i)d(j)[gcd(i,j)=1])

对着(sum_{i=1}^{n/g}sum_{j=1}^{m/g} d(i)d(j)[gcd(i,j)=1])施展莫比乌斯反演可转化为一个辣鸡，所以这条路GG了。

真做法:

考虑如下这个式子，(d(ij)=sum_{u|i}sum_{v|j}[gcd(u,v)=1])

为什么成立呢？我们考虑质因子(p)在(i,j)中的指数。设(p)在(i)中出现(a_1)次，在(j)中出现(a_2)次，那么(p)在(i*j)的因子中就会有(a_1+a_2+1)种选择。然后我们考虑等式右边，当(gcd(u,v)=1)，设(u)中(p)的指数为(b_1)，(v)中(p)的指数为(b_2),那么(b_1=0)或者(b_2=0), 合法的有序对((b_1,b_2))共有(a_1+a_2+1)个。然后，每种质因子相互独立。所以等式是成立的。

然后这个问题就简单了。不妨设(n<m)

原式 = (sum_{i=1}^{n}sum_{j=1}^{m}sum_{u|i}sum_{v|j} [gcd(u,v)=1])

交换求和顺序得 (sum_{u=1}^{n}sum_{v=1}^{m} [frac{n}{u}] [frac{m}{v}] [gcd(u,v)=1])

施展莫比乌斯反演得(sum_{d=1}^{n} mu(d) sum_{i=1}^{n/d}sum_{j=1}^{m/d}frac{n/d}{i}frac{m/d}{j} = sum_{d=1}^{n} mu(d) (sum_{i=1}^{n/d}frac{n/d}{i})(sum_{j=1}^{m/d}frac{m/d}{j}))

施展跳跳狗分块，即可。

栗子4: ZOJ3881

做法:

先观察到(f(x))是积性函数，然后(g(n)=sum_{d|n}f(d))也是积性函数。
(g(n)=(p_1^{a_1}+1)(p_2^{a_2}+1)(p_3^{a_3}+1).....) 【喵】
展开(g(n))我们可以发现，(g(n)=sum_{d|n} d[gcd(d,n/d)=1])
(sum_{i=1}^{n} g(i) = sum_{i=1}^{n}sum_{d|i}d[gcd(d,i/d)=1])
按照(gcd(d,n/d))的值，进行容斥有(sum_{g=1}^{sqrt n}mu(g)sum_{i=1}^{n/g^2}i*[frac{n/g^2}{i}])
跳跳狗分块即可。复杂度(O(sqrt nlog(sqrt n)))

【喵】：这个地方，还是打表来得舒适。接下来我们来推一推。

考虑质数(p),(g(p)=p+1),(g(p^k)=p^k+1)
根据积性函数的性质，证完了。【积性函数太好用了！】【口胡.jpg】