[蓝桥杯 2018 国 B] 矩阵求和

Luogu
IDLGP8670
Time2000ms
Memory256MB
DifficultyP5
2018数论容斥原理蓝桥杯国赛
经过重重笔试面试的考验,小明成功进入 Macrohard 公司工作。 今天小明的任务是填满这么一张表: 表有 $n$ 行 $n$ 列,行和列的编号都从 $1$ 算起。 其中第 $i$ 行第 $j$ 个元素的值是 $\gcd(i, j)$ 的平方,$\gcd$ 表示最大公约数,以下是这个表的前四行的前四列: ``` 1 1 1 1 1 4 1 4 1 1 9 1 1 4 1 16 ``` 小明突然冒出一个奇怪的想法,他想知道这张表中所有元素的和。 由于表过于庞大,他希望借助计算机的力量。 ## Input 一行一个正整数 $n$ 意义见题。 ## Output 一行一个数,表示所有元素的和。由于答案比较大,请输出模 $1000000007$(即$10^9+7$)后的结果。 [samples] ## Note 对于 $30\%$ 的数据,$n\le 1000$。 存在 $10\%$ 的数据,$n = 10^5$。 对于 $60\%$ 的数据,$n\le 10^6$。 对于 $100\%$ 的数据,$n\le 10^7$。
Samples
Input #1
4
Output #1
48
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2018 国 B] 矩阵求和",
    "description": {
      "content": "经过重重笔试面试的考验,小明成功进入 Macrohard 公司工作。 今天小明的任务是填满这么一张表: 表有 $n$ 行 $n$ 列,行和列的编号都从 $1$ 算起。 其中第 $i$ 行第 $j$ 个元素的值是 $\\gcd(i, j)$ 的平方,$\\gcd$ 表示最大公约数,以下是这个表的前四行的前四列: ``` 1  1  1  1 1  4  1  4 1  1  9  1 1  4 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8670"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "经过重重笔试面试的考验,小明成功进入 Macrohard 公司工作。\n\n今天小明的任务是填满这么一张表:\n\n表有 $n$ 行 $n$ 列,行和列的编号都从 $1$ 算起。\n\n其中第 $i$ 行第 $j$ 个元素的值是 $\\gcd(i, j)$ 的平方,$\\gcd$ 表示最大公约数,以下是这个表的前四行的前四列:\n\n```\n1  1  1  1\n1  4  1  4\n1  1  9  1\n1  4 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments