RXD and math

                                                                    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)                                                                                             Total Submission(s): 1035    Accepted Submission(s): 570 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   Source 2017 Multi-University Training Contest - Team 3  

题意：给出一个n和k，求出题目给出的式子

解题思路：其实就是一个莫比乌斯函数，打表找规律后发现就是求n^k

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; const LL mod=1000000007; LL n,k; LL mypow(LL a,LL b) { LL ans=1; a%=mod; while(b) { if(b&1) {ans*=a;ans%=mod;} a=(a*a)%mod; b>>=1; } return ans; } int main() { int cas=0; while(~scanf("%lld%lld",&n,&k)) { printf("Case #%d: %lld\n",++cas,mypow(n,k)); } return 0; }