自动搬运

查看原文

来自洛谷，原作者为

	tbdsh 到，天边去生活？|| AFOed on 2025.07.07 || 最后在线时间：2025年8月18日19时14分

搬运于2025-08-24 22:41:17，当前版本为作者最后更新于2024-02-23 15:06:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简述

题目传送门

更好的阅读体验

给定 $n(1\le n\le 10^7)$，求 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}\gcd(i,j)^2 \bmod (10^9+7)$。

分析

首先可以用 $O(n^2)$ 的时间复杂度打出一个 $\gcd(i,j)^2$ 的表：

我们想要求出 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}\gcd(i,j)^2$，那么就是求 $C_{\gcd(i,j)^2} \times \gcd(i,j)^2$，其中，$C_{\gcd(i,j)^2}$ 指 $\gcd(i,j)^2$ 在上述 $n\times n$ 的矩阵中的出现次数。

同时可以发现，$\gcd(i,j)^2$ 与 $\gcd(i,j)$ 一一对应，且如果序列中位置 $(i,j)$ 的值是 $\gcd(i,j)$，那么应该有 $C_{\gcd(i,j)}=C_{\gcd(i,j)^2}$。所以下文中我们用 $C_{\gcd(i,j)}$ 代替 $C_{\gcd(i,j)^2}$ 。

我们联想一下：在一个 $4\times 4$ 的矩阵中，$\gcd(2,2)^2=4$ 应该在这四个位置中出现：$(2,2),(2,4),(4,2),(4,4)$。但是，位置 $(4,4)$ 的值 $\gcd(4,4)^2=16$ 占掉了 $\gcd(2,2)^2=4$ 的位置。所以 $\gcd(2,2)^2$ 的出现次数应该是 $4-C_{\gcd(4,4)}=3$。

进一步的，我们可以发现：如果位置 $(i,j)$ 的值为 $x=\gcd(i,j)$，那么所有值为 $kx(k\ge 2)$ 的位置都会占用 $x$ 的位置。

那么，在不考虑占用的情况下，令 $x=\gcd(i,j)$，$C_{x}=(\left\lfloor \dfrac{n}{x}\right\rfloor)^2$。由于存在占用，那么 $C_{x}\gets C_x-\sum\limits^{\lceil \frac{n}{x} \rceil}_ {k=2}C_{kx}$。

可以注意到，此时我们需要的遍历顺序是 $n\sim 1$。

最终答案就是 $\sum\limits^n_{i=1}C_i\times i^2\bmod(10^9+7)$。

时间复杂度：$O(n\ln n)$。

空间复杂度：$O(n)$。

Code

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int Mod = 1e9 + 7, MAXN = 1e7 + 5;
int cnt[MAXN];
signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, ans = 0;
  cin >> n;
  for (int i = n; i >= 1; i--){
    cnt[i] = (n - n % i) / i * (n - n % i) / i;
    for (int j = 2; i * j <= n; j++){
      cnt[i] -= cnt[i * j];
    }
    (ans += i * i % Mod * (cnt[i] % Mod)) %= Mod;
  }
  cout << ans;
  return 0;
}