AT_abc162_e [ABC162E] Sum of gcd of Tuples (Hard)

题目描述

考虑由 $1$ 到 $K$ 之间的整数构成的长度为 $N$ 的数列 $\{A_1, \ldots, A_N\}$。

这样的数列共有 $K^N$ 个。请你计算所有这些数列的 $\gcd(A_1, \ldots, A_N)$ 的和。

由于答案可能非常大，请输出该和除以 $10^9+7$ 的余数。

其中，$\gcd(A_1, \ldots, A_N)$ 表示 $A_1, \ldots, A_N$ 的最大公约数。

输入格式

输入以以下格式从标准输入读入。

$N$ $K$

输出格式

请输出所有 $K^N$ 个数列的 $\gcd(A_1, \ldots, A_N)$ 的和除以 $10^9+7$ 的余数。

输入输出样例 #1

输入 #1

3 2

输出 #1

9

输入输出样例 #2

输入 #2

3 200

输出 #2

10813692

输入输出样例 #3

输入 #3

100000 100000

输出 #3

742202979

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$
• 输入均为整数

样例解释 1

$\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)=1+1+1+1+1+1+1+2=9$，因此答案为 $9$。

样例解释 3

请输出该和除以 $10^9+7$ 的余数。

由 ChatGPT 4.1 翻译