ACM模版

描述

题解

这个题是一道推导题，推导过程如下：

首先，我们应该都知道的是

n=∑d|nphi(d)
所以呢，
∑i=1ni=∑i=1n∑d|iphi(d)
goon…
∑i=1ni=∑i=1nphi(i)∗⌊ni⌋
此时，我们来分析题目中的式子，设 F(x)=∑ni=1phi(i)∗⌊ni⌋ ，恰好等于上述 ∑ni=1 。

所以呢，我们的结果也就出来了，先预处理前 232 个 phi ，然后求等差数列的和，减去前 232 个，接着求出后 232 个 phi ，并减去，当然这里要注意肯定不是直接减去，还要先乘以 ⌊ni⌋ 再减去，就这样，没问题了。

代码

#include <iostream>
#include <cmath>

#define clr(x,y) memset(x, y, sizeof(x))

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAGIC = 233;

int n;
int phi[MAGIC];

int get_phi(int x)
{
    unsigned i, res = x;    // unsigned == unsigned int
    for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
    {
        if (!(x % i))
        {
            res = res / i * (i - 1);
            while (!(x % i))
            {
                x /= i;     // 保证i一定是素数
            }
        }
    }
    if (x > 1)
    {
        res = res / x * (x - 1);
    }
    return res;
}

void init()
{
    for (int i = 1; i <= MAGIC; i++)
    {
        phi[i] = i;
    }
    for (int i = 2; i <= MAGIC; i += 2)
    {
        phi[i] /= 2;
    }
    for (int i = 3; i <= MAGIC; i += 2)
    {
        if (phi[i] == i)
        {
            for (int j = i; j <= MAGIC; j += i)
            {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

int main()
{
    init();

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        int ans = (ll)n * (1 + n) / 2 % MOD;
        for (int i = 1; i < MAGIC; i++)
        {
            ans = (ans - (ll)phi[i] * (n / i) % MOD + MOD) % MOD;
        }
        for (int i = n; i > n - MAGIC; i--)
        {
            ans = (ans - (ll)get_phi(i) * (n / i) % MOD + MOD) % MOD;
        }

        cout << ans << endl;
    }

    return 0;
}