HDOJ 1420 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): 8103    Accepted Submission(s): 3098

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暑期集訓隊練習賽（二）​​

最最基礎的快速幂，方法務必要掌握。

#include <stdio.h>
int main()
{
  __int64 a,b,c,N,ans;
  scanf("%I64d",&N);
  while(N--)
  {
    scanf("%I64d%I64d%I64d",&a,&b,&c);
    ans = 1;
    a = a % c;
    while(b)
    {
      if(b % 2 == 1)
        ans = (ans * a) % c;
      b = b/2;
      a = (a * a) % c;
    }
    printf("%I64d\n",ans);
  }
  return 0;
}