小魔现主义（0）

Spouter_27 · 2023-09-28 11:34:21 · 个人记录

小魔现主义 洛谷篇（编号为非正）

正篇发表于 bilibili 账号 SPST清屿市第一中学。

线性筛约数个数

• 求一个数约数个数：

根据算数基本定理，一个数 x(x\ge 2) 可唯一拆解成

的形式，其中 p_i 为不同素数且由 p_1 到 p_n 递增。那么 x 的约数个数 d(x) 为

证明很好证，考虑任何一个 y=p_1^{l_1}p_2^{l_2}\dots p_n^{l_n},其中 0\le l_i\le k_i 那么 y 一定是 x 的因数。而 l_1\dots l_n 总共有 (1+k_1)(1+k_2)\dots (1+k_n) 种不同的选法。

• 线性筛最小质因数个数：

设 num(x) 表示 x 的最小质因数个数。

注意 num(1) 无定义。

先放代码：

typedef long long ll;

ll num[N],prime[N],cnt=0;
bool vis[N];
void initd(ll n){
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            num[i]=1;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]<=n){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0){
                    num[i*prime[j]]=num[i]+1;
                    break;
                }
                num[i*prime[j]]=1;
            }
            else{
                break;
            }
        }
    }
}

说明之前未被扫过， i 为质数。

由于 prime[j] 是从小往大数的，所以 prime[j] 就是 i 的最小质因数。同时 i\times prime[j] 的最小质因数也是 prime[j] ，个数为 num(i)+1 。

此时 prime[j] 小于 i 的最小质因数， i\times prime[j] 的最小质因数为 prime[j] ，个数为 1 。

假设 x=p_1^{k_1}p_2^{k_2}\dots p_n^{k_n} 且 x 不是素数，如果 k_1=1 ，那么 x 会且仅会在 y=p_2^{k_2}\dots p_n^{k_n} 被 y 更新。否则 x 会且仅会在y=p_1^{k_1-1}p_2^{k_2}\dots p_n^{k_n} 被 y 更新。如果 x 未被更新，则 x=p_1，即 x 为质数。由此可见时间复杂度为 O(n) ， n 即要筛的值域。

• 约数个数线性筛：

特判： d(1)=1 。

typedef long long ll;

ll d[N],num[N],prime[N],cnt=0;
bool vis[N];
void initd(ll n){
    d[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            num[i]=1;
            d[i]=2;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]<=n){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0){
                    num[i*prime[j]]=num[i]+1;
                    d[i*prime[j]]=d[i]/(num[i]+1)*(num[i]+2);
                    break;
                }
                d[i*prime[j]]=d[i]*2;
                num[i*prime[j]]=1;
            }
            else{
                break;
            }
        }
    }
}

就是在线性筛最小质因数个数的基础上添加了求 d 的过程。

说明i为质数，含有两个因数1和i。