Min_25筛

$$ \\ \text{设素数集合}P,P_i\text{表示第}i\text{个素数,}P_1=2 \\ \text{设积性函数}F\left( x \right) ,\text{在}x\text{为质数时满足}F\left( x \right) =f\left( x \right) \\ \text{设}g\left( n,k \right) \text{为}n\text{范围内，质数和最小质因子大于}P_k\text{的数的}f\left( x \right) \text{之和} \\ \text{即把}f\left( 1 \right) ,f\left( 2 \right) …f\left( n \right) \text{这些数写出来，运行埃氏筛}k\text{次后，没被筛掉的数}+\text{素数的}f\text{函数的和} \\ g\left( n,k \right) \text{可以以类似于递推的形式进行转移。} \\ \text{如果}P_k^2>n \\ \text{此时}g\left( n,k \right) =g\left( n,k-1 \right) \\ \text{这时候运行筛法筛不掉任何东西。} \\ \text{如果}P_k^2\le n \\ \text{那么}g\left( n,k \right) =g\left( n,k-1 \right) -\left( \text{最小质因子恰好为}P_k\text{的数的影响} \right) \\ \text{我们筛掉所有最小质因子为}P_k\text{的数} \\ g\left( n,k \right) =\begin{cases} g\left( n,k-1 \right) \left( P_{k}^{2}>n \right)\\ g\left( n,k-1 \right) -f\left( p_k \right) \left( g\left( \frac{n}{p_k},k-1 \right) -\sum_{1\le i\le k-1}{f\left( p_i \right)} \right) \left( P_{k}^{2}\le k \right)\\ \end{cases} \\ -\sum_{1\le i\le k-1}{f\left( P_i \right)}\text{表示把最小质因子不是}P_i\text{的质数减掉，这些数不应该参与这次筛。} \\ \text{最终,}g\left( n,|P| \right) \text{表示}n\text{范围内，所有质数的}f\left( x \right) \text{之和。} \\ \text{即运行完埃氏筛后筛出来的数之和。} \\ \text{这部分的复杂度是}O\left( \frac{n^{\frac{3}{4}}}{\log\text{ }n} \right) \\ \text{然后如何求积性函数前缀和？} \\ \text{设}S\left( n,k \right) \text{表示}n\text{之内，最小质因子大于等于}P_k\text{的}F\left( x \right) \text{之和} \\ \text{首先统计}n\text{范围内,大于等于}P_k\text{质数的贡献为}g\left( n,|P| \right) -\sum_{1\le i\le k-1}{F\left( P_i \right)} \\ \text{然后暴力枚举大于等于}P_k\text{的质因子及其出现次数,根据积性函数的性质统计答案}. \\ \text{注意要额外加上}f\left( P_i^{e+1} \right) ,\text{因为}S\left( \frac{n}{P_i^e},i+1 \right) \text{不包括}f\left( P_i^e \right) \\ S\left( n,k \right) =g\left( n,|P| \right) -\sum_{1\le i\le k-1}{F\left( P_i \right)}+\sum_{i\ge k\,\,and\,\,P_i^2\le n}{\sum_{e\ge \text{1 }and\,\,P_i^{e+1}\le n}{\left( S\left( \frac{n}{P_i^e},i+1 \right) f\left( P_i^e \right) +f\left( P_i^{e+1} \right) \right)}} \\ \text{则}\sum_{1\le i\le n}{F\left( i \right)}=F\left( 1 \right) +S\left( n,1 \right) \\ $$

https://www.luogu.org/problemnew/show/P4213

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <map>
#include <assert.h>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 1e6;
int_t primes[LARGE + 1];

int_t primeCount = 0;
int_t hash1[LARGE + 1], hash2[LARGE + 1];
int_t numbers[LARGE + 1];
//g0- f(x)=1
//g1 -f(x)=x
int_t g0[LARGE + 1], g1[LARGE + 1];
int_t sum0[LARGE + 1], sum1[LARGE + 1];
int_t sqr;
int_t n;
int_t S2(int_t x)
{
    return x * (x + 1) / 2;
}

void process(int_t n)
{
    static bool isPrime[LARGE + 1];
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = false;
    for (int_t i = 2; i <= n; i++)
    {
        for (int_t j = i * i; j <= n; j += i)
        {
            isPrime[j] = false;
        }
    }
    for (int_t i = 1; i <= n; i++)
    {
        if (isPrime[i])
        {
            primes[++primeCount] = i;
            sum0[primeCount] = sum0[primeCount - 1] + 1;
            sum1[primeCount] = sum1[primeCount - 1] + i;
        }
    }
}

//返回n以内，最小质因子大于等于p_k的数的欧拉函数之和
int_t Sphi(int_t n, int_t k)
{
    if (n <= 1 || primes[k] > n)
        return 0;

    int_t result = 0;
    if (n <= sqr)
        result += g1[hash1[n]] - g0[hash1[n]];
    else
        result += g1[hash2[::n / n]] - g0[hash2[::n / n]];
    //统计质数贡献的答案
    result -= sum1[k - 1] - sum0[k - 1];
    //枚举质因子
    for (int_t i = k; primes[i] * primes[i] <= n && i <= primeCount; i++)
    {
        for (int_t p = primes[i], e = 1; p * primes[i] <= n; p = p * primes[i], e++)
        {
            result += Sphi(n / p, i + 1) * (p - p / primes[i]) + (p * primes[i] - p);
        }
    }
    return result;
}

int_t Smu(int_t n, int_t k)
{
    if (n <= 1 || primes[k] > n)
        return 0;

    int_t result = 0;
    if (n <= sqr)
        result += -g0[hash1[n]];
    else
        result += -g0[hash2[::n / n]];
    //统计质数贡献的答案
    result -= -sum0[k - 1];
    //枚举质因子
    for (int_t i = k; primes[i] * primes[i] <= n && i <= primeCount; i++)
    {
        result += Smu(n / primes[i], i + 1) * -1;
    }
    return result;
}

void process()
{
    cin >> n;
    sqr = ::sqrt(n);
    numbers[0] = 0;
    for (int_t i = 1, next = 1; i <= n; i = next + 1)
    {
        next = n / (n / i);
        numbers[++numbers[0]] = n / i;
        if (n / i <= sqr)
        {
            hash1[n / i] = numbers[0];
        }
        else
        {
            hash2[n / (n / i)] = numbers[0];
        }
        g0[numbers[0]] = (n / i) - 1;
        g1[numbers[0]] = S2(n / i) - 1;
    }
    for (int_t j = 1; j <= primeCount; j++)
    {
        for (int_t i = 1; i <= numbers[0] && primes[j] * primes[j] <= numbers[i]; i++)
        {
            int_t trans = 0;
            if (numbers[i] / primes[j] <= sqr)
            {
                trans = hash1[numbers[i] / primes[j]];
            }
            else
            {
                trans = hash2[n / (numbers[i] / primes[j])];
            }
            g0[i] = g0[i] - (g0[trans] - sum0[j - 1]);
            g1[i] = g1[i] - primes[j] * (g1[trans] - sum1[j - 1]);
        }
    }
    cout << Sphi(n, 1) + 1 << " " << Smu(n, 1) + 1 << endl;
}
int main()
{
    process(1e6);
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++)
    {
        process();
    }
    return 0;
}