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

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

题目描述

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

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

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

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

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

输入格式

一行两个正整数 NNkk

输出格式

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

样例

样例输入 1

4 2

样例输出 1

8

样例输入 2

666 233

样例输出 2

2539518298

数据范围与提示

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

子任务编号 分值 NN kk
1 55 1000\leq 1000 2×109\leq2 \times 10^9
2 1212 105\leq 10^5 2×109\leq2 \times 10^9
3 1818 107\leq 10^7 2×109\leq2 \times 10^9
4 1515 2×109\leq 2 \times 10^9 =1=1
5 5050 2×109\leq 2 \times 10^9 2×109\leq 2 \times 10^9