BZOJ3944 杜教筛

(被owenowl要求加上的内容)flx 教我杜教筛,虽然他没做这道题。

传送门,戳这里

Problem

Description

题目

Input

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个 非负整数N,代表一组询问

Output

一共T行,每行两个用空格分隔的数ans1,ans2

Sample

Input

Output

Solution

杜教筛裸题。

下面是我学杜教筛的一点经验,和大家分享一下。
如果您已经精通杜教筛,请跳过下面的内容,直接看注意事项。

如果您还不会莫比乌斯反演,请先学习反演再看本文。否则,可能一头雾水。

一般求Phi函数和mu函数都用线性筛,可以在O(n)的时间内求出1~n的所有phi值和mu值。下面是线性筛的代码,主要思想就是筛质数,然后根据phi和mu的积性函数性质筛后面的数。

Markdown炸了。。没法打数学公式。。

但是对于n很大求前缀和的情况(比如本题),O(n)的复杂度就不够了。这个时候就需要一种新的方法————杜教筛。

设h = f ⊗ g,设f的前缀和为S,而h的前缀和易求,那么可以用杜教筛。经过推导,可以得到:
杜教筛公式

首先考虑对μ函数的前缀和(欧拉函数同理):
构造一个g(i)=1!那么,有:

M(x)为mu[x]的前缀和:

求phi函数的时候,如何构造g(x)留给读者自行思考。

杜教筛关键在于构造g函数与f函数进行卷积,再通过杜教筛的公式递归求值。(可以是另一个杜教筛)
有几个注意事项:

1、首先,在用杜教筛之前,先用线性筛把开始较小的一些数(1~n^(2/3))的phi和mu给筛出来,再调用杜教筛,这样可以优化一下复杂度。

2、在用杜教筛枚举i求phi(x/i)时,分段枚举,对于一段x/i相同的i的区间只枚举一次,再乘以这一段的大小即可。否则可能会T掉

3、对于线性筛筛出来的值,要用数组存,不要用map,否则会多一个log,很可能T掉;

Code bzoj 3944

附上AC代码,前几十行写了读入优化,可以跳过。
本题AC需要靠运气,或者您去学洲阁筛吧。