2018年第九届蓝桥杯国赛-F. 矩阵求和

2022-05-26 · 103次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #算法竞赛 #数学

题面

原题链接

【问题描述】

经过重重笔试面试的考验，小明成功进入 Macrohard 公司工作。

今天小明的任务是填满这么一张表：

表有 n 行 n 列，行和列的编号都从1算起。其中第 i 行第 j 个元素的值是 $gcd(i, j)$ 的平方，gcd 表示最大公约数，以下是这个表的前四行的前四列：

小明突然冒出一个奇怪的想法，他想知道这张表中所有元素的和。

由于表过于庞大，他希望借助计算机的力量。

【输入格式】

一行一个正整数 n 意义见题。

【输出格式】

一行一个数，表示所有元素的和。由于答案比较大，请输出模 (10⁹ + 7)(即：十亿零七) 后的结果。

【样例输入】

【样例输出】

【数据范围】

对于 30% 的数据， $n \le 1000$ 。

存在 10% 的数据， $n = 10^5$ 。

对于 60% 的数据， $n \le 10^6$ 。

对于 100% 的数据， $n \le 10^7$ 。

思路

数论，欧拉函数

可以看yxc大佬的视频讲解，秒懂，传送门，直接看 1 时 56 分。具体就不在赘述。

代码

#include<iostream>

using namespace std;
typedef long long LL;
const int N = 1e7 + 5, MOD = 1e9 + 7;
int prime[N], tot;
LL s[N], phi[N];
bool v[N];

//预处理 质数 和 欧拉函数
void pre(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!v[i]) {
            phi[i] = i - 1;
            prime[++tot] = i;
        }
        for (int j = 1; j <= tot && i <= n / prime[j]; j++) {
            v[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }

    s[1] = phi[1];
    for (int i = 2; i <= n; i++) s[i] = (s[i - 1] + 2 * phi[i]) % MOD;
}

int main() {
    int n;
    cin >> n;
    pre(n);

    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + s[n / i] * i % MOD * i % MOD) % MOD;
    }
    cout << ans << endl;

    return 0;
}

标题：	2018年第九届蓝桥杯国赛-F. 矩阵求和
链接：	https://www.fightingok.cn/detail/236
更新：	2022-09-18 22:50:36
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可