P8670 [蓝桥杯 2018 国 B] 矩阵求和 题解

· · 题解

题意简述

题目传送门

更好的阅读体验

给定 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;
}