Sum of gcd of Tuples (Hard)

题目描述

考虑长度为 $N$ 的序列 $\{A_1,...,A_N\}$，元素为介于 $1$ 到 $K$（含）之间的整数。 共有 $K^N$ 个这样的序列。求所有序列的 $\gcd(A_1, ..., A_N)$ 之和。 由于该和可能非常大，输出结果对 $(10^9+7)$ 取模。 这里 $\gcd(A_1, ..., A_N)$ 表示 $A_1, ..., A_N$ 的最大公约数。

输入格式

输入按照下列格式由标准输入提供： $N$ $K$

输出格式

输出对 $(10^9+7)$ 取模的所有 $K^N$ 个序列的 $\gcd(A_1, ..., A_N)$ 之和。

3 2

9

3 200

10813692

100000 100000

742202979

提示

$2 \leq N \leq 10^5$ $1 \leq K \leq 10^5$ 输入中的所有数值均为整数。$\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$。
请确保输出对 $(10^9+7)$ 取模的和。

标签: AtCoder|abc162E

来源

AtCoder|abc162E