#572. 「LibreOJ Round #11」Misaka Network 与求和

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

一方通行成功接入了 Misaka Network。

现在他要使用超能力,自然计算式被送到了御坂网络进行处理。这次的计算式是这样子的:

\sum_{i=1}^{N}\sum_{j=1}^{N}f(\gcd(i,j))^k \bmod 2^{32}

其中 f(x) 表示 x 次大的质因数,重复的质因数计算多次,例如 f(6)=2,f(4)=2 。规定 f(1)=0,f(p)=1 ,其中 p 为质数。

但是妹妹们都不会算这个式子……所以御坂 20001 号找到了你,希望你帮她算一下。

输入格式

一行两个正整数 N k

输出格式

一行一个整数,表示答案。

样例

样例输入 1

4 2

样例输出 1

8

样例输入 2

666 233

样例输出 2

2539518298

数据范围与提示

对于所有数据 1 \leq N,k \leq 2 \times 10^9

子任务编号 分值 N k
1 5 \leq 1000 \leq2 \times 10^9
2 12 \leq 10^5
3 18 \leq 10^7
4 15 \leq 2 \times 10^9 =1
5 50 \leq 2 \times 10^9