hdu1420 Prepared for New Acmer （快速幂模）

Prepared for New Acmer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

​

Total Submission(s): 7683    Accepted Submission(s): 2909

Problem Description

集訓進行了将近2個禮拜，這段時間以恢複性訓練為主，我一直在密切關注大家的訓練情況，目前為止，對大家的表現相當滿意，首先是絕大部分隊員的訓練積極性很高，其次，都很遵守集訓紀律，最後，老隊員也起到了很好的帶頭作用，這裡特别感謝為這次DP專題練習賽提供題目和測試資料的集訓隊隊長xhd同學.

特别高興的是，跟随集訓隊訓練的一批新隊員表現非常好，進步也比較顯著，特别是訓練态度大大超出我的預期，我敢說，如果各位能如此堅持下去，絕對前途無量！

考慮到新隊員還沒有經過系統訓練，我這裡特别添加一道簡單題：

給定三個正整數A，B和C（A,B,C<=1000000），求A^B mod C的結果.

希望各位都能體會到比賽中AC的快樂，絕對的量身定制，很高的待遇喲，呵呵...

Input

輸入資料首先包含一個正整數N,表示測試執行個體的個數，然後是N行資料，每行包括三個正整數A,B,C。

Output

對每個測試執行個體請輸出計算後的結果，每個執行個體的輸出占一行。

Sample Input

3

2 3 4

3 3 5

4 4 6

Sample Output

2

4

Author

lcy

Source

​​ACM暑期集訓隊練習賽（二）​​

Recommend

lcy   |   We have carefully selected several similar problems for you:  

​​1060​​​ 

​​​1568​​​ 

​​​3641​​​ 

​​​1788​​​ 

​​​3430​​ 

代碼：

#include<cstdio>
using namespace std;

typedef long long LL;

int main()
{
  freopen("1.in","r",stdin);
  int n;  LL ans,a,b,c;
  scanf("%d",&n);
  while(n--)
    {
      scanf("%I64d%I64d%I64d",&a,&b,&c);
      ans=1;
      while(b)
        {
          if(b&1)ans*=a,ans%=c;
          a=(a*a)%c,b>>=1;
    }
    printf("%I64d\n",ans);
  }
  return 0;
}