对于各种数论函数的前缀和,如果线性跑不过去,
那就可以尝试复杂度为 $ O(n^{2/3}) $ 的杜教筛,
听说还有 min_25 筛,洲阁筛等一堆乱七八糟的筛法

前置技能:
– 基本数论函数
– 狄利克雷卷积
– 整除分块

设要求 $ S(n) = \sum_{i=1}^n f(i) $
找到函数 g, h 令 $ h = f \cdot g $
则:
$$ \sum_{i=1}^n h(i) $$
$$ = \sum_{i=1}^n\sum_{d|i}f(\frac{i}{d}) \cdot g(d)$$
$$ = \sum_{d=1}^ng(d) \cdot \sum_{i=d}^nf(\frac{i}{d}) \cdot [i|d]$$
$$ = \sum_{d=1}^ng(d) \cdot \sum_{i=1}^{n/d}f(i)$$
$$ = \sum_{d=1}^ng(d) \cdot S(\frac{n}{d})$$
$$ = g(1) \cdot S(n) + \sum_{d=2}^ng(d) \cdot S(\frac{n}{d})$$
所以 $S(n) = \sum_{i=1}^n h(i) – \sum_{d=2}^n g(d) \cdot S(\frac{n}{d})$
如果 h 的前缀和容易求,那后面一大块就是整除分块的套路了
经分析得不考虑h的前缀和复杂度为 $O(n^{2/3})$ ,
其实我根本不知道怎么来的

洛谷模板P4213
欧拉函数的前缀和可以用莫比乌斯反演,光用杜教筛会被卡,作为例子,只贴出杜教筛的代码
实际应用中需要注意:
– 一般要记录求得的 $ S(n) $
– 一般先线性晒出前 maxn 的 S(n), maxn 的值一般在 $ \sqrt{n} $ 左右?

很久以前写的代码,不用你们喷,我也知道很 shi :

#pragma GCC optimize(2)
#include <bits/stdc++.h>

inline long long input() { long long res; scanf("%lld",&res); return res; }

const int maxn = 5000000;
int mu[maxn] , phi[maxn];
long long s_mu[maxn] , s_phi[maxn];
bool not_prime[maxn];
std::vector<int> prime;

void init()
{
    not_prime[1] = true;
    mu[1] = 1;
    phi[1] = 1;
    for(int i=2;i<maxn;i++)
    {
        if(not not_prime[i])
            mu[i] = -1 ,
            phi[i] = i - 1 ,
            prime.push_back(i);
        for(uint j=0;j<prime.size();j++)
        {
            long long p = prime[j];
            if(i * p >= maxn) break;
            not_prime[i * p] = true;
            if(i % p == 0)
            {
                mu[i * p] = 0;
                phi[i * p] = phi[i] * p;
                break;
            }
            mu[i * p] = mu[i] * -1;
            phi[i * p] = phi[i] * (p - 1);
        }
    }
    s_mu[1] = mu[1];
    s_phi[1] = phi[1];
    for(int i=2;i<maxn;i++)
        s_mu[i] = s_mu[i - 1] + mu[i] ,
        s_phi[i] = s_phi[i - 1] + phi[i] ;
}

long long ans_mu(long long n)
{
    if(n < maxn) return  s_mu[n];
    static std::unordered_map<long long , long long> mp;
    if(mp.count(n)) return mp[n];
    long long res = 1;
    for(int l=2,r;l<=n;l=r)
    {
        r = n / (n / l) + 1;
        res -= ans_mu(n / l) * (r - l);
    }
    return mp[n] = res;
}

long long ans_phi(long long n)
{
    if(n < maxn) return s_phi[n];
    static std::unordered_map<long long , long long> mp;
    if(mp.count(n)) return mp[n];
    long long res = (n + 1) * n >> 1;
    for(int l=2,r;l<=n;l=r)
    {
        r = n / (n / l) + 1;
        res -= ans_phi(n / l) * (r - l);
    }
    return mp[n] = res;
}

int main()
{
    int T = input();
    init();
    while(T --)
    {
        int n = input();
        printf("%lld %lld\n",ans_phi(n),ans_mu(n));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注