P10186 [YDOI R1] Lattice 题解
Starstream
·
·
题解
思路
引理 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
***
#### 引理 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})$。
### 代码
```cpp
#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;
}
```