【分析】
等价于分析
\(\quad ans\)
\(\displaystyle =\sum_{i=1}^n \boldsymbol \mu^2(i)\lfloor\sqrt {n\over i}\rfloor\)
考虑莫比乌斯函数 \(\boldsymbol \mu(n)\) 不为 \(0\) 时的取值一定为 \(\pm 1\)
故 \((\forall n\to \boldsymbol \mu(n)\neq 0)\to \boldsymbol \mu^2(n)=1\)
而使得 \(\boldsymbol \mu(n)\neq 0\) ，则 \(\not\exists p^2\to p^2\mid n(p\in Prime)\)
考虑每个 \(t=a^2\cdot b\) 的形式（\(a\) 是极大的形式），则 \(\boldsymbol \mu^2(b)=1\)
考虑将正整数集 \(Z\) ，按上述 \(b\) 进行归纳，会发现，对于 \(\forall n\in Z\) ，有且仅有一个 \(b\) 使得 \(n\) 被归纳进 \(b\) 所在的集合
因此该归纳构成对正整数集 \(Z\) 的一个划分
故对于 \([1,n]\) 范围内每个 \(b\) ，设其所在集合为 \(H_b\) ，则 \(|H_b|=\lfloor\sqrt {n\over b}\rfloor\)
存在 \(1\) 个 \(a(a=1)\) 使得 \(\boldsymbol \mu^2(a^2\cdot b)=1\)
且存在 \((\sqrt{n\over b}-1)\) 个 \(a\) 使得 \(\boldsymbol \mu^2(a^2\cdot b)=0\)
则 \(H_b\) 对求和式的贡献为 \(\displaystyle \sum_{a^2\cdot b\leq n}\boldsymbol \mu^2(a^2\cdot b)\lfloor\sqrt {n\over a^2\cdot b}\rfloor=\boldsymbol \mu^2(b)\lfloor\sqrt{n\over b}\rfloor+0=\lfloor\sqrt {n\over b}\rfloor=|H_b|\)
故对于所有的 \(H_b\) 的贡献求和得到 \(\displaystyle ans=\sum_{b\leq n}|H_b|=n\)
故对于原题，直接得到答案为 \(n^k\)
记得先取模再快速幂即可
【代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1e9+7;
inline ll fpow(ll a,ll x) { ll ans=1; for(a%=P;x;x>>=1,a=a*a%P) if(x&1) ans=ans*a%P; return ans; }
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,k;
for(int i=1;cin>>n>>k;++i)
cout<<"Case #"<<i<<": "<<fpow(n,k)<<"\n";
cout.flush();
return 0;
}