一、題目

1、題目描述

經過重重筆試面試的考驗，小明成功進入 Macrohard 公司工作。

今天小明的任務是填滿這么一張表：

表有?�n?行?�n?列，行和列的編號都從?11?算起。

其中第?�i?行第?�j?個元素的值是?gcd?(�,�)gcd(i,j)?的平方，gcd?gcd?表示最大公約數，以下是這個表的前四行的前四列：

1  1  1  1
1  4  1  4
1  1  9  1
1  4  1 16

小明突然冒出一個奇怪的想法，他想知道這張表中所有元素的和。 由于表過于龐大，他希望借助計算機的力量。

2、輸入輸出

2.1輸入

一行一個正整數?�n?意義見題。

2.2輸出

一行一個數，表示所有元素的和。由于答案比較大，請輸出模?10000000071000000007（即109+7109+7）后的結果。

3、原題鏈接

P8670 [藍橋杯 2018 國 B] 矩陣求和 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

---

二、解題報告

1、思路分析

先對公式進行化簡

我們外層枚舉需要O(n)的時間復雜度，那么對于f[k]的計算有沒有快速的方法？

1  1  1  1
1  4  1  4
1  1  9  1
1  4  1 16

以示例為例，我們先考慮以2為公因數（注意并非gcd）的(i，j)數，顯然有[4 / 2] * [4 / 2] = 4個

而此時矩陣中有3個2，原因是第四個2被16替代了，因為4作為比2大的數是(4，4)的gcd

因此我們可以得出以k為gcd的(i，j)數為[n / k] * [n/ k] - f[j]（j為k的倍數）

這樣就得到了f[]的轉移方程，這個狀態轉移是O(lnn)的

注意寫代碼時若干運算的選擇，很可能因為多進行一次取模而導致沒過

nlnn對于1e7數據量而言還是有點慢

2、復雜度

時間復雜度： O(nlnn)空間復雜度：O(n)

3、代碼詳解

?

#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int N = 1e7 + 10, mod = 1e9 + 7;
int n, f[N], res = 0;
void solve()
{cin >> n;for (int i = n; i >= 1; i--){f[i] = ((n / i) * (n / i)) % mod;for (int j = i << 1; j <= n; j += i)f[i] = (f[i] - f[j] + mod) % mod;res = (res + f[i] * (i * i) % mod) % mod;}cout << res;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);//freopen("in.txt", "r", stdin);int _ = 1;while (_--)solve();return 0;
}