HDU 6063-RXD and math

連結：http://acm.hdu.edu.cn/showproblem.php?pid=6063

Problem Description

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

莫比烏斯反演 ， 他們 說國小奧賽都學過 ，但我 沒發處理那個階乘，

是以 就10^10 mod 1e9+7 發現 剛好等于答案 ，然後 就開始了 暴力之路 。

但要注意2點 ， 階乘用 快速幂 别傻傻的for循環， 就是每次* 的前後 和開始都要取模

代碼：

#include<bits/stdc++.h>
#define mod 1000000007
//#define mod 1e9+7
using namespace std;
long long pow(long long a,long long b)
{
   long long int ans = ,base = a;
    while(b!=)
    {
        if(b&){
            base%=(long long)mod;
            ans%=(long long)mod;
            ans *= base;
            ans%=(long long)mod;
        }
        base%=(long long)mod;
        base *= base;
        base%=(long long)mod;
        b>>=;
    }
    return ans;
}
int main()
{
    long long int n,k;
    int t=;
    while(~scanf("%lld %lld",&n,&k)){
            t++;
        printf("Case #%d: ",t);
        printf("%lld\n",pow(n,k));
    }
    return ;
}
           

順便附上 整數快速幂 講解：

http://blog.csdn.net/changjiale110/article/details/76467887