51Nod-1237-最大公约数之和 V3

ACM模版

描述

题解

发现 51Nod 上题号为 123∗ 的几个题连着都是杜教筛，俨然可以成为一个模版搞搞了……但是我的数学水平实在有限，就算搞了模版怕是也无法灵活使用，所以想想也就算了。

其实早先我是不知道分块具体是指什么的，做了这几道杜教筛的问题后，我算是搞明白这个，就是我们最后获取的公式是一个递归式，所以我们可以将整个问题划分为两部分，小的部分打表出来，而大的部分，可以依靠递归式来求解，当然，这也许只是我的一个狭隘的认知，实在是对这些个概念懵懵懂懂的。

具体的推导过程，给大家分享一个大牛的链接，实在是对 LaTeX 的公式写的手抽筋儿，所以懒得再絮絮叨叨的写一堆推导了，dance_in_the_dark’s blog 公式推导相当详细，大牛说很容易就推出来了，这让我这数学 zz 和公式恐惧症很尴尬啊……只能 Orz 一下了，希望有一天我也可以将自己的数学水平提高到不再畏惧~~~

代码

#include <iostream>
#include <cstdio>

#define ll long long

using namespace std;

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INV_2 = 5e8 + 4;

ll pri[MAXN];
ll vis[MAXN];
ll phi[MAXN];
ll h[MAXN * 10];
ll f[MAXN * 10];
ll n, ans;

int hash_(ll x)
{
    int t = x % MAXN;
    while (h[t] && h[t] != x)
    {
        t = (t + 1) % MAXN;
    }
    return t;
}

ll Gphi(ll n)
{
    if (n <= MAXN)
    {
        return phi[n];
    }

    ll x = hash_(n);
    if (h[x])
    {
        return f[x];
    }

    ll t = n % MOD;
    ll k = t * (t + 1) % MOD * INV_2 % MOD;
    for (ll i = 2; i <= n; i = t + 1)
    {
        t = n / (n / i);
        k -= Gphi(n / i) * (t - i + 1) % MOD;
    }
    k = (k % MOD + MOD) % MOD;
    h[x] = n;
    f[x] = k;
    return k;
}

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

            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            else
            {
                phi[i * pri[j]] = phi[i] * phi[pri[j]];
            }
        }
    }
    for (int i = 1; i <= MAXN; i++)
    {
        phi[i] += phi[i - 1];
    }
}

int main()
{
    init();

    scanf("%lld", &n);

    ll t, l, k;
    for (ll i = 1; i <= n; i = t + 1)
    {
        t = n / (n / i);
        k = (Gphi(t) - Gphi(i - 1) + MOD) % MOD;
        l = n / i % MOD;
        ans = (ans + l * l % MOD * k % MOD) % MOD;
    }

    printf("%lld\n", ans);

    return 0;
}