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

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

题目描述

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

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

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

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

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

输入格式

一行两个正整数 NNNkkk

输出格式

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

样例

样例输入 1

4 2

样例输出 1

8

样例输入 2

666 233

样例输出 2

2539518298

数据范围与提示

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

子任务编号 分值 NNN kkk
1 555 ≤1000\leq 10001000 ≤2×109\leq2 \times 10^92×109
2 121212 ≤105\leq 10^5105 ≤2×109\leq2 \times 10^92×109
3 181818 ≤107\leq 10^7107 ≤2×109\leq2 \times 10^92×109
4 151515 ≤2×109\leq 2 \times 10^92×109 =1=1=1
5 505050 ≤2×109\leq 2 \times 10^92×109 ≤2×109\leq 2 \times 10^92×109