数的阶乘幂 && 洛谷 U132839 幂（数学，快速幂）

传送门

解题思路

先看一下数据范围，a、b、c都是10^6，所以大体推断出做法时间复杂度约为nlogn。

根据a^xy=（a^x）^y，所以a^b！=(((((a^1)^2)^3)^4)^……)^b。

用底数变化的快速幂（O（logb））做b次即可。

或者对指数b!做一些处理——

我们知道指数b!一定不能直接mod，但是我们把b! mod一个x，使得结果不变。

其中x要保证a^xmod c=1。很显然，这样做就等于把b!-kx，等于a^b!/a^kx，结果不变。

怎么保证一定有这个x呢？

我们把a¹，a²，a³……a^c%c写出来

当存在一个x使得a^x%c=0时，只需判断b!是否大于等于x，若大于等于，结果为0，否则结果直接快速幂算即可。
若不存在x使得a^x%c=0，那么我们不妨设不存在a^x%c=1，即a^k%c ε [2，c-1]（k：1~c）。那么一定存在两个数s和t(s>t)，a^s%c=a^t%c。那么很显然，a^s-t%c=1。这与假设相违背，所以一定存在这个x。

所以这两种做法都可以过此题，第一种O(nlogn)，第二种O(n)。

另外看60分做法，模数是质数，我们可以想到费马小定理——a^p-1%p=1，这时，c-1即是我们要找的x。

AC代码（第一种做法）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 long long a,b,c;
 7 long long kuaisumi(long long a,int x){
 8     if(x==1) return a%c;
 9     long long ans;
10     if(x&1) ans=a%c;
11     else ans=1;
12     long long kkk=kuaisumi(a,x/2);
13     ans=ans*kkk%c*kkk%c;
14     return ans;
15 }
16 long long work(long long a,long long b){
17     while(b>0){
18         a=kuaisumi(a,b);
19         b--;
20     }
21     return a%c;
22 }
23 int main(){
24     cin>>a>>b>>c;
25     cout<<work(a,b)%c<<endl;
26     return 0;
27 }