题目内容

对于给定的整数$n$，对于全部的二元组$(i,j)$满足$1≦i<j≦n$，计算$\frac{i+j}{gcd{i,j}}$之和。由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

$gcd$，即最大公因数，指两个整数共有约数中最大的一个。例如，$12$和 $30$的公约数有$1,2,3,6$，其中最大的约数是$6$，因此$gcd(12,30) =6$。

小歪的数字问题

题解思路

1. 题目要求计算所有满足 1 ≤ i < j ≤ n 的二元组 $(i,j)$ 对应的值
   $\frac{i+j}{\gcd(i,j)}$
   的总和，并对 $10^9+7$ 取模。

2. 注意到令 $d=gcd(i,j)$，令 $i=d \cdot a, j=d\cdot b$ 且 $\gcd(a,b)=1$（且 $a<b$），有