Problem Description

RXD is a good mathematician.

One day he wants to calculate:

∑i=1nkμ2(i)×⌊nki−−−√⌋

output the answer module 109+7.

1≤n,k≤1018

μ(n)=1(n=1)

μ(n)=(−1)k(n=p1p2…pk)

μ(n)=0(otherwise)

p1,p2,p3…pk are different prime numbers

Input

There are several test cases, please keep reading until EOF.

There are exact 10000 cases.

For each test case, there are 2 numbers n,k.

Output

For each test case, output "Case #x: y", which means the test case number and the answer.

Sample Input

10 10

Sample Output

Case #1: 999999937

分析：

u()函数是莫比乌斯函数，这个不影响做题,这个式子算的是[1,n^k]中能够写成(a×b^2)的数的个数,其中|u(a)|=1.然后我们可以证明任何数都可以唯一写成(a×b^2)的形式，因为(b = p1p2..pn),假设(a)中没有(b)中的因子，那么肯定是唯一表示的，如果(a)中含有(b)中的因子，改变表示的形式，那么肯定要将(b)改变，假设将任意一个(p)和(a)中的某个不在(b)中的质因子互换时，由于(p)无论在(a)中本来有或没都无法构成平方，所以无法互换，表达形式唯一。以这个式子会把[1, n^k]的每个整数恰好算一次. 所以答案就是n^k。

或则可以直接自己打表看一下简单的规律，比赛的时候就是自己写了几组数据找出来的规律。

#include
    
     #include
     
      typedef long long ll;const int  mod=1e9+7;ll n,k;using namespace std;void solve(ll n,ll k){    ll ans=1;    ll res=n;    while(k)    {        if(k&1)            ans=((ans%mod)*(res%mod))%mod;        res=((res%mod)*(res%mod))%mod;        k>>=1;    }    printf("%lld\n",ans);}int main(){    int Case=1;    while(~scanf("%lld%lld",&n,&k))    {        printf("Case #%d: ",Case++);        solve(n,k);    }    return 0;}
     
    

​​