题目链接
题意
求解
∑i=1nkμ2(i)×⌊nki−−−√⌋
其中
μ(n)=1(n=1)
,
μ(n)=(−1)k(n=p1p2p3…pk)
,
其他情况μ(n)=0(其他情况)
分析
=-=赛时暴力打表，发现答案刚好等于
nk
，套个快速幂即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
#define LL long long
const int mod=
1e9+
7;
int isprime[
100100];
LL quick_pow(LL a,LL b){
LL ret=
1;
while(b){
if(b&
1)
ret=(a*ret)%mod;
b>>=
1;
a=(a*a)%mod;
}
return ret;
}
int main(){
LL n,k;
int cas=
1;
while(~
scanf(
"%I64d %I64d",&n,&k)){
LL ans=quick_pow(n%mod,k);
printf(
"Case #%d: %I64d\n",cas++,ans);
}
}
