#P9258. 奇妙数论题

    ID: 5379 传统题 1500ms 512MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-欧拉函数交换求和顺序线性筛倍数枚举稀疏状态重置

奇妙数论题

题目描述

小 ZZ 在学习数论的时候想到一个这样的问题。

给你一个长为 nn 的 排列 aa ,求

∑i=1n∑j=1n(ai,aj)\sum_{i = 1}^{n} \sum_{j = 1}^{n} (a_i, a_j)

注意 (ai,aj)(a_i, a_j) 表示 gcd⁡(ai,aj)\gcd(a_i, a_j) ,也就是 ai,aja_i, a_j 的最大公约数。

小 XX 看了一眼,说道这不是道裸题吗,然后把小 ZZ 吊了一顿。

于是小 ZZ 想了想如何加强,于是多加了一个乘数。

给你一个长为 nn 的 排列 aa ,求

$$\sum_{i = 1}^{n} \sum_{j = 1}^{n} (a_i, a_j) \cdot (i, j)$$

小 XX 又认真看了看,又说“有什么区别”。

小 ZZ 没有办法加强了,十分无奈地把这题丢了出来给聪明的你做。

输入格式

第一行两个正整数 nn 。

接下来一行共 nn 个正整数,其中第 ii 个表示 aia_i 。

输出格式

输出一行一个数,表示答案,对于 109+710^9 + 7 取模。

5
1 4 5 2 3
73

数据范围与提示

保证 n≤105n \le 10^5 且 aia_i 为一个 排列 。