LOJ6053 简单的函数

Min_25筛板子.

注意到对于质数$p$,$f(p)=p-1(p\geq 3)$,而对于$2$,$f(2)=3$.

所以先默认对于所有质数,$f(p)=p-1$,拆成两个函数$h(x)=x$和$g(x)=1$,分别按照Min25筛里求出来$g_0(n,k)$和$g_1(n,k)$即可。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <inttypes.h>
using int_t = long long int;

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

const int_t mod = 1000000007;
const int_t LARGE = 1e6;

int_t hash1[LARGE + 1], hash2[LARGE + 1];
int_t sum0[LARGE + 1], sum1[LARGE + 1];
int_t g0[LARGE + 1], g1[LARGE + 1];
int_t primes[LARGE + 1];
int_t numbers[LARGE + 1];
int_t sqr;
int_t n;
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++)
    {
        if (isPrime[i])
        {
            primes[++primes[0]] = i;
            sum0[primes[0]] = (sum0[primes[0] - 1] + 1) % mod;
            sum1[primes[0]] = (sum1[primes[0] - 1] + i) % mod;
#ifdef DEBUG
            cout << "sum0 " << primes[0] << " = " << sum0[primes[0]] << endl;
            cout << "sum1 " << primes[0] << " = " << sum1[primes[0]] << endl;

#endif
            for (int_t j = i * i; j <= LARGE; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}

int_t S(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]] + 2 * mod) % mod;
    else
        result += (g1[hash2[::n / n]] - g0[hash2[::n / n]] + 2 * mod) % mod;
    result = (result - (sum1[k - 1] - sum0[k - 1]) + 2 * mod) % mod;
#ifdef DEBUG
    cout << "S " << n << ",k(" << primes[k] << ") prime answer = " << result << endl;
#endif
    for (int_t i = k; i <= primes[0] && primes[i] * primes[i] <= n; i++)
    {
        for (int_t p = primes[i], j = 1; p * primes[i] <= n; p *= primes[i], j++)
        {
            //应该是去查质因子大于等于P_{i+1},而不是k+1(因为已经把i+1的除掉了)
            result = (result + S(n / p, i + 1) * (primes[i] ^ j) + ((primes[i]) ^ (j + 1))) % mod;
        }
    }
#ifdef DEBUG
    cout << "S " << n << "," << k << "(" << primes[k] << ") = " << result << endl;
#endif
    return result;
}

int main()
{
    const auto S2 = [](int_t x) -> int_t { return (__int128_t)x * (x + 1) / 2 % mod; };
    cin >> n;
    if(n==1){
         cout<<1<<endl;
         return 0;
    }
    
    sqr = sqrt(n);
    process(sqr);
    for (int_t i = 1, next; 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];
        //numbers[0]写成numbers[i]
        g0[numbers[0]] = n / i - 1;
        g1[numbers[0]] = S2(n / i) - 1;
    }
    for (int_t j = 1; j <= primes[0]; j++)
    {
        for (int_t i = 1; i <= numbers[0] && primes[j] * primes[j] <= numbers[i]; i++)
        {
            int_t trans;
            //要判断numbers[i]/primes[j]而不是别的
            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]) + mod * 2) % mod;
            //primes[j]没写
            g1[i] = (g1[i] - primes[j] * (g1[trans] - sum1[j - 1]) + mod * 2) % mod;
#ifdef DEBUG
            cout << "G0 " << numbers[i] << "," << j << "(" << primes[j] << ") = " << g0[i] << endl;
            cout << "G1 " << numbers[i] << "," << j << "(" << primes[j] << ") = " << g1[i] << endl;

#endif
        }
    }
    //忘了加上1的情况
    cout << (S(n, 1) + 3) % mod << endl;
    return 0;
}