2022 软件学院 ACM 集训队筛选赛

Problem A. Frontier Tripper

Frontier tripper, Tianjiang, has created the universe, which consists of countless worlds, one of which is called the Blue Planet. Unfortunately, the first-created world's logic is defective and thus has caused some fatal errors. After millions of years, the errors gathered together and formed the Abyss.

However, after creating the universe, the Creator Tianjiang has lost most of his power. So he was unable to fix these errors temporarily. To get the power again, He's now going on a long trip to the frontier of the universe.

The destination of the trip is a party for creators of all universes. They holds regular competitions, which is named International Casually Playing Competition, or famous as ICPC. The top 210 competitors would gained strong power. Competitors are firstly ranked by the number of games they played successfully, if same, then they'd be ranked by the total used time. In the last 46th ICPC on April 17, Tianjiang was knocked out because he was 26 seconds behind and only played 2 games. He got the time used time of 4:44:37 while the 210th competitor got 4:44:11.

Since he failed last time lacking of math thinking. He'd like train himself with lots of math problems. And here's one easy math problem:

For an integer n , define \varphi(n) as the number of positive integers from [1,n] that co-prime with n , and define \sigma(n) as the sum of all the positive divisors of n .

Given n,k , you need to calculate \sum_{i=1}^n\varphi(i^k)\cdot\sigma(i^k) modulus 10^9+7 .

输入

Input two integers n,k(1\le n,k\le10^6) .

输出

Output one integer (\sum_{i=1}^n\varphi(i^k)\cdot\sigma(i^k))\bmod(10^9+7) .

样例

标准输入 复制文本
6 1
标准输出 复制文本
74
标准输入 复制文本
6 2
标准输出 复制文本
2053
标准输入 复制文本
580 581
标准输出 复制文本
652051863

提示

For example, if n=6 , then \varphi(6)=2 because two numbers 1,5 are co-prime with 6 , and \sigma(6)=12 because all the positive divisors are 1,2,3,6 and 1+2+3+6=12 .

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 52
通过 5

A B C D E F G H

鉴于过题情况不理想,比赛时间延长1小时,22:00开始封榜。
可以尝试一下做D,G或H题。
C题是签到题。
请注意题目难度与题目顺序无关。