(不知不觉又给自己挖了个坑.)
ckr : “我只是在无敌的路上越走越远”
洲阁筛食用方法
食用范围
大部分的情况差不多这样:
给出一个积性函数$f(x)$满足积性函数的基本性质,$f(1)=1$,如果$gcd(a,b)=1$有$f(ab)=f(a)f(b)$.
那么根据唯一分解定理,就是$x=\prod _{i=1}^np_i^{k_i}$就可以:
$In \space particular,p \space\space is\space a\space prime\space number$，而且$f(p^c)$可以快速求出.
一般的题目差不多都这样:
$f(x)$是一个数论函数,要求$\sum_{i=1}^nf(i)$,而且你发现,杜教筛完全不能用卷积简化，你被题目的形式深深卡死！
啊♂
洲阁筛就出现了。
食用思想
主要的核心思想在于:分类
引理：$n$以内的数,最多只有一个大于$\sqrt{n}$的质因数:
$Proof:$
假设原命题不成立,即存在有两个大于$\sqrt{n}$的质因数,
那么不妨设这两个质因数是$n_1,n_2$ 于是有$n_1n_2>n$,但这是不可能的！
$\therefore$假设命题不成立，原命题正确.