题目详情题解（0）讨论（0）提交记录（0）

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

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

考虑由 11 到 KK 之间的整数构成的长度为 NN 的数列 {A1,…,AN}\{A_1, \ldots, A_N\}。

这样的数列共有 KNK^N 个。请你计算所有这些数列的 gcd⁡(A1,…,AN)\gcd(A_1, \ldots, A_N) 的和。

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

其中，gcd⁡(A1,…,AN)\gcd(A_1, \ldots, A_N) 表示 A1,…,ANA_1, \ldots, A_N 的最大公约数。

输入格式

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

NN KK

输出格式

请输出所有 KNK^N 个数列的 gcd⁡(A1,…,AN)\gcd(A_1, \ldots, A_N) 的和除以 109+710^9+7 的余数。

输入输出样例

  • 输入#1

    3 2

    输出#1

    9

  • 输入#2

    3 200

    输出#2

    10813692

  • 输入#3

    100000 100000

    输出#3

    742202979

说明/提示

限制条件

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤K≤1051 \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\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，因此答案为 99。

样例解释 3

请输出该和除以 109+710^9+7 的余数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页