杜教筛

和式变换基础¶

首先基本函数有 $\mu,\varphi$。

Euler Sieve

C++
bool isNotPrime[N];

int prime[N], cnt, mu[N];

long long phi[N];

void EulerSieve()

{

    mu[1]=1; phi[1]=1;

    for(int i=2; i<N; i++)

    {

        if(!isNotPrime[i])

        {

            prime[++cnt]=i;

            mu[i]=-1;

            phi[i]=i-1;

        }

        for(int j=1; j<=cnt&&prime[j]*i<N; j++)

        {

            isNotPrime[prime[j]*i]=true;

            if(i%prime[j]==0)

            {

                mu[prime[j]*i]=0;

                phi[prime[j]*i]=phi[i]*prime[j];

                break;

            }

            mu[prime[j]*i]=-mu[i];

            phi[prime[j]*i]=phi[prime[j]]*phi[i];

        }

    }

    return;

}

instance¶

天梯赛 L3-3 可怜的简单题

式子推导不难，处理无穷求和是转化去一个等比数列。总之需要求的结果就是

\[ \sum\limits_{t=1}^{n}\mu(t) +n\sum\limits_{t=2}^{n}\frac{1}{\lfloor\frac{n}{t}\rfloor-n}\mu(t) \]

inference¶

Note that factor with $\lfloor\rfloor$ just has $O(\sqrt n)$ different values, divided into continous segments. So basically the difficulty lies in the prefix sum of $\mu$.

Practice

Prove that

\[ \sum\limits_{i=1}^{n} \mu(i) = 1 - \sum\limits_{t=2}^{n}\sum_{i=1}^{\lfloor n/t\rfloor}\mu(i) \]

Step1

Actually the technique here is re-combine the $\mu$ s by different direction, in $\sum_{k=1}^{n} [k=1]$. List $[k=1]$ s' $\mu$ s, row-ly. Column-ly combine them, to get $$ 1 = \sum\limits_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor $$

Step2

proceed to transform the sum into prefix-like form, based on the index in the $\mu$.

By observing that $\{\lfloor \frac{n}{d}\rfloor:d=1,\cdots,n\}$ is a ladder-shaped stuff, which was just mentioned in above content. We can exhaustively to make them into prefix-like form.

Technically, the process can also be visualized as row-ly to column-ly. Just imagine $\mu(k)$ corresponds a row with length $\lfloor\frac{n}{k}\rfloor$. The details and result will be clarified in the following step.

Step3

Enumerate $t = 1,2,\cdots, n$, refers the position on the row of $\mu(1)$ (obviously the length is $n$), right now we're considering. The limit we can column-ly stretch, is the max $\boxed{X}$ which satisfies

\[ \lfloor\frac{n}{\boxed{X}}\rfloor \ge t \]

The tricky technique here is that we can remove the $\lfloor\rfloor$ equivalently.

Then the thing is easy
$$ \frac{n}{t} \ge \boxed{X} $$ So $$ \boxed{X} = \lfloor\frac{n}{t}\rfloor $$

Example

The principle of Division-Segmentation can be proved in the similar way in step3

So how to efficiently take advantage of the recursion-like formula?

algorithm¶

Denote that

$$ S_n := \sum\limits_{i=1}^{n} \mu(i) $$ Calculate $n=1,\cdots,M$ in advance, do the recursion, then the time complexity should be

$$ O(M+\frac{N}{\sqrt{M}}) $$ So let $M = O(N^{2/3})$ to get $O(N^{2/3})$.

The details of the analysis can refer 杜教筛 - OI Wiki. The usage of memorization lies in the fact

$$ \lfloor\frac{\lfloor\frac{n}{x}\rfloor}{y}\rfloor = \lfloor\frac{n}{xy}\rfloor $$ swap $x,y$ vice versa. So the possible value we may visit is really limited, corresponding to the very divisor.