【数论】指数取余

题目描述
输入整数m，n，k，求mn mod k的值。m，n，k*k为长整型范围内的自然数。

输入
输入一行3个整数，分别为m，n和k。

输出
输出一行一个整数，表示结果。

样例输入
复制样例数据
2 10 9
样例输出
7

#include<bits/stdc++.h>
using namespace std;
typedef long int ll;
int main()
{
  ll m,n,k;
  cin>>m>>n>>k;
  ll res=1%k;
  while(n)
  {
    if(n&1) res=res*m%k;
    m=m*m%k;
    n>>=1;
  //  cout<<res<<endl;
  }
  cout<<res<<endl;
}