Hdu 6063 - RXD and math（思维）

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6063

题目大意：
求式子$\sum_{i=1}^{n^k}\mu^2(i)\times\lfloor \sqrt{\frac{n^k}{i}}\rfloor$的值

分析：
根据多校第三场的1008题解，任意一个数$x$，可以被唯一的表示成$a^2\times b$的形式，其中$\mu^2(b) = 1$，对于小于$n^k$的每一个$\mu^2(i)=1$的$i$来说，$\lfloor \sqrt{\frac{x}{i}} \rfloor$表示$a^2\times i \leq x$的所有a的个数，由于对于每个$i$，能表示出的数均不同，所以小于$n^k$的所有的$i$恰好能表示出$n^k$内的所有数，所以答案就是$n^k$，快速幂即可

注意：由于$n,k$均为$10^{18}$级别，所以如果快速幂前不对n取模，过程中会爆long long

代码：

 
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long ll;
const int mod = 1e9+7;

ll quickpow(ll a,ll n)
{
    ll res= 1;
    while (n)
    {
        if (n&1)
            res = res*a%mod;
        a = a*a%mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    ll n,k;
    int t = 1;
    while (~scanf("%lld%lld",&n,&k))
    {
        ll ans =quickpow(n%mod,k);
        printf("Case #%d: %lld\n",t++,ans%mod);

    }
    return 0;
}