Phantom Bird

外观

线性筛

约 571 字大约 2 分钟

OIOI-notemaths

2025-6-26

今天晚自习被 GooodPig 和 Function 拉去解决他们关于 τ(n)\tau(n) 的猜想.

故复习了下线性筛.

线性筛要求：每个合数都被它最小的质因数筛掉. 它不仅能够保证效率，而且最小质因数的性质为我们求 τ(n)\tau(n) 有很大的帮助.

学习线性筛，先要改变一下观念. 寻常的筛是将一个质数的所有倍数筛掉，而线性筛的写法是：把一个数的所有质数倍筛掉. 显然两者是等价的.

我们记 nn 的最小质因数为 mp(n)\mathrm{mp}(n)，要使得 p=mp(i×p)p = \mathrm{mp}(i \times p)，必须满足：p≤mp(i)p \le \mathrm{mp}(i).

于是，我们搜到 p=mp(i)p = \mathrm{mp}(i) 之后，直接 break，就实现了线性筛.

bool notp[maxn];
vector<int> primes;

void sieve(int n) {
    notp[1] = true;
    
    for(int i = 2; i <= n; i++) {
        if(!notp[i]) {
            primes.push_back(i);
        }
            
        for(int p: primes)
        {
            notp[i * p] = true;
            if(i %  p == 0)
                break;
        }
    }
}

τ

我们知道，

τ(n)=∏p(1+vp(n))\tau(n) = \prod_p (1+v_p(n))

其中 vp(n)v_p(n) 代表 nn 的质因数分解的 pp 对应的指数

设 p=mp⁡(n),n=i×pp = \operatorname{mp}(n), n = i \times p，则有

τ(n)τ(m)=1+vp(n)1+vp(m)={vp(m)+2vp(m)+1,p=mp⁡(m)2,otherwise\frac{\tau(n)}{\tau(m)} = \frac{1 + v_p(n)}{1 + v_p(m)} = \begin{cases} \dfrac{v_p(m) + 2}{v_p(m) + 1}, & p = \operatorname{mp}(m) \\ 2, & \text{otherwise} \end{cases}

而 vp(n)+1v_p(n) + 1 正是右式的分母，以下代码中的 mft 也是指这个值.

以下是输出 τ(n)\tau(n) 的前缀最大值的代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=1e6+10;

vector<int> primes;
bool is_not_prime[maxn];
int tau[maxn];
int mft[maxn];


signed main() {
    int n;
    cin >> n;
    
    tau[1] = 1;
    mft[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        if (!is_not_prime[i]) {
            primes.push_back(i);
            tau[i] = 2;
            mft[i] = 2;
        }

        for (int p: primes) {
            if (i * p > n){
                  break;
            }
            
            is_not_prime[i*p] = true;
            
            
            if (i % p == 0){
                tau[i*p] = tau[i] / mft[i] * (mft[i] + 1);
                mft[i*p] = mft[i] + 1;
            } else {
                tau[i*p] = tau[i] * 2;
                mft[i*p] = 2;
            }
            
            
            if (i % p == 0){
                  break;
            }
        }

    }
    
    int pmax=-0x3f3f3f3f3f3f3f3f;
    for (int i=1; i<=n; i++){
        if (tau[i] > pmax){
            printf("%d ", tau[i]);
            pmax = tau[i];
        }
    }

    return 0;
}

积性函数

事实上，对于任何积性函数 ff，如果可以在 O(t(n))O(t(n)) 的时间算出 f(pn)f(p^n)，那么，可以在 O(nt(n))O(nt(n)) 内筛出 f(1),…,f(n)f(1), \dots, f(n).

设 p=mp⁡(n),n=pk×m,p∤mp=\operatorname{mp}(n), n=p^k\times m, p \nmid m，则

f(n)=f(pk)×f(m).f(n) = f(p^k) \times f(m).

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)