Kickstart 2017 Round G: Problem A

Abridged problem statement

Compute  A^N! % P

Constraints

1 ≤ T ≤ 100.

Small dataset

1 ≤ A ≤ 10.
1 ≤ N ≤ 10.
1 ≤ P ≤ 10.

Large dataset

1 ≤ A ≤ 10⁵.
1 ≤ N ≤ 10⁵.
1 ≤ P ≤ 10⁵.

Approach  

Just use the fact that 

A^m*n = (A^m)ⁿA^m*n % P = ( (A^m % P)ⁿ % P )

Code

#include <iostream>
using namespace std;

int power(long long x, int n, int M){

  long long result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;

}

int main(){

  freopen("A-large-practice.in", "r", stdin);
  freopen("output-large.txt", "w", stdout);

  int t, a, n, p;
  long long ans;

  cin>>t;

  for(int i=1; i <=t; i++){
    cin>>a>>n>>p;

    ans = a;

    for(int i=1; i<=n; i++){
      ans = power(ans, i, p);
    }

    cout<<"Case #"<<i<<": "<<ans<<endl;
  }
}