ACM模版

描述

题解

这个题和那个 51Nod 1244 莫比乌斯函数之和 的方法几乎一模一样，差别就是推导公式的结果不一样罢了，但是形式是一样的。

推导如下：
设

f(n)=∑i=1nφ(i)
通过欧拉函数的性质我们可以知道：
∑d|nφ(d)=n
所以呢，
φ(n)=n−∑d|n,d<nφ(d)
f(n)=∑i=1n(i−∑d|i,d<iφ(d))
f(n)=n∗(n+1)2−∑i=2n∑d|i,d<iφ(d)
f(n)=n∗(n+1)2−∑i=2n∑d=1⌊ni⌋φ(d)
f(n)=n∗(n+1)2−∑i=2nf(⌊ni⌋)

公式的形式和 莫比乌斯函数之和 的款式是一样的，所以求解方法也是一样的，依然是分块儿和记忆化等操作。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MOD1 = 1e9 + 7;
const int MOD2 = 2333333;
const int INV_2 = 5e8 + 4;
const int MAXN = 5e6 + 10;

ll n;
int tot;
ll tep[MOD2];
ll val[MOD2];
int phi[MAXN + 5];
int prime[MAXN + 5];
int hed[MOD2];
int net[MOD2];
bool vis[MAXN + 5];

void add(int x, ll y, ll z)
{
    tep[++tot] = y;
    val[tot] = z;
    net[tot] = hed[x];
    hed[x] = tot;
}

ll cal(ll x)
{
    if (x <= MAXN)
    {
        return phi[x];
    }

    int k = x % MOD2;
    ll ret = 0, z = x % MOD1;
    for (int i = hed[k]; i; i = net[i])
    {
        if (tep[i] == x)
        {
            return val[i];
        }
    }
    for (ll l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        ret += (r - l + 1) % MOD1 * cal(x / l) % MOD1;
        ret %= MOD1;
    }
    ret = (z * (z + 1) % MOD1 * INV_2 % MOD1 - ret + MOD1) % MOD1;
    add(k, x, ret);
    return ret;
}

void init()
{
    for (int i = 2; i <= MAXN; i++)
    {
        if (!vis[i])
        {
            prime[++prime[0]] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= prime[0]; j++)
        {
            int k = i * prime[j];
            if (k > MAXN)
            {
                break;
            }
            vis[k] = 1;
            if (!(i % prime[j]))
            {
                phi[k] = phi[i] * prime[j];
                break;
            }
            phi[k] = phi[i] * (prime[j] - 1);
        }
    }

    phi[1] = 1;
    for (int i = 1; i <= MAXN; i++)
    {
        phi[i] += phi[i - 1];
        phi[i] %= MOD1;
    }
}

int main()
{
    init();

    scanf("%lld", &n);
    printf("%lld", cal(n));

    return 0;
}