2000ms

Difficulty: 10

所属公司 : 饿了么

时间 :2025年3月17日(后端方向)

算法与标签>数学

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

小歪的数字问题

题解思路

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

题目内容

对于给定的整数 $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$ 。