自动搬运

查看原文

来自洛谷，原作者为

	Starstream 退役叻 | 期待与你重逢，庆幸与你同频。

搬运于2025-08-24 22:55:33，当前版本为作者最后更新于2024-02-25 18:14:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

引理 1

在一个 $n\times n$ 的点阵中，如果直线经过的第 $1$ 个点为 $(x, y)$，则它经过的点数目为 $\lfloor \dfrac{n}{\max(x, y)} \rfloor$。

证明

若直线经过的第一个点为 $(x, y)$，则第二个点为 $(2x, 2y)$。

以此类推，经过的最后一个点坐标为 $(kx, ky)(k\in \mathbb N^*)$。

$$1\le kx \le n,1\le ky \le n$$

解得：

$$1\le k \le \min(\lfloor\dfrac{n}{x}\rfloor,\lfloor\dfrac{n}{y}\rfloor)=\lfloor \dfrac{n}{\max(x, y)} \rfloor $$

$k$ 共有 $\lfloor \dfrac{n}{\max(x, y)} \rfloor$ 种取值，即共经过 $\lfloor \dfrac{n}{\max(x, y)} \rfloor$ 个点。

---

引理 2

在一个 $n\times n$ 的点阵中，如果直线经过的第 $1$ 个点为 $(x, y)$，则 $\gcd(x, y)=1$。

证明

假设直线经过的第 $1$ 个点为 $(x, y)$，且 $\gcd(x, y) \ne 1$。

则必定存在一个点 $\left(\dfrac{x}{\gcd(x, y)},\dfrac{y}{\gcd(x, y)}\right)$ 被直线经过。该点横纵坐标互质，且更靠近原点。

这说明点 $(x, y)$ 不是第一个被经过的点。

结论与假设矛盾，引理 2 得证。

---

发现原图贡献是轴对称的，所以我们可以只计算上半边贡献。

$$\sum_{i=2}^n\sum_{j=1}^{i-1}\lfloor \dfrac{n}{\max(i, j)} \rfloor^2[\gcd(i, j) = 1] $$$$\sum_{i=2}^n\sum_{j=1}^{i-1}\lfloor \dfrac{n}{i} \rfloor^2[\gcd(i, j) = 1] $$

原式可以通过欧拉函数计算，代入得：

$$\sum_{i=2}^n\varphi(i)\times\lfloor \dfrac{n}{i} \rfloor^2 $$

再考虑对角线的贡献，共 $n$ 个点，贡献为 $n^2$。

所以答案为：

$$n^2+2\times \sum_{i=2}^n\varphi(i)\times\lfloor \dfrac{n}{i} \rfloor^2 $$

尽管 $\lfloor \dfrac{n}{i} \rfloor^2$ 可以整除分块，但是 $2\times 10^9$ 的线性复杂度前缀和不可接受，于是想到用杜教筛计算。

时间复杂度 $O(n^\frac{2}{3})$。

代码

#include <iostream>
#include <unordered_map>
#define int __int128

using namespace std;

const int N = 6000010, mod = 1e9 + 7;

int n;
long long m;
int primes[N], cnt;
int phi[N], s[N];
unordered_map<long long, int> me;
bool st[N];

inline void get_euler(int n) // 线性筛 6e6 以内的欧拉函数值
{
    st[1] = true, phi[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i, phi[i] = i - 1;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

int get_sum(int n) // 杜教筛板子
{
    if (n < N) return s[n];
    if (me[n]) return me[n];
    int res = n * (n + 1) / 2;
    for (int l = 2, r = 0; l <= n; l = r + 1)
    {
        r = n / (n / l);
        res = (res - (r - l + 1) * get_sum(n / l) % mod) % mod;
    }
    return me[n] = res;
}

signed main()
{
	get_euler(N - 1);
	for (int i = 1; i < N; i ++ )
		s[i] = (s[i - 1] + phi[i]) % mod;

	scanf("%lld", &m), n = m;
	int res = 0;
	for (int l = 2, r = 0; l <= n; l = r + 1)
	{
		r = n / (n / l); // 整除分块
		res = (res + (n / l) * (n / l) % mod * (get_sum(r) - get_sum(l - 1)) % mod) % mod;
	}

	res = res * 2 % mod;
	res = (res + n * n % mod) % mod;
	printf("%lld\n", (long long)((res + mod) % mod));
	return 0;
}