一方通行成功接入了 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=1∑Nj=1∑Nf(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 号找到了你,希望你帮她算一下。
一行两个正整数 NNN 和 kkk。
一行一个整数,表示答案。
4 2
8
666 233
2539518298
对于所有数据 1≤N,k≤2×1091 \leq N,k \leq 2 \times 10^91≤N,k≤2×109。