题目链接

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<iostream>

#include<stdio.h>

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;

}

​​