1.定义***
费马小定理是数论中的一个定理。其内容为假如a是一个整数，p是一个质数的话，那么:
a^p = a(mod p)
假如a不是p的倍数的话，那么这个定理也可以写成:
a^(p ? 1) = 1(mod p)
这个书写方式更加常用些。
2.费马小定理的证明***
任意取一个质数，比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12，给这些数都乘上一个与13互质的数，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说，这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12，只是顺序不同而已。
把1,2,3,?,12统统乘起来，乘积就是12的阶乘12！。把3,6,9,?,36也统统乘起来，并且提出公因子3，乘积就是312×12！。对于模13来说，这两个乘积都同余于1,2,3,?,12系列，尽管顺序不是一一对应，即312×12！≡12！mod 13。两边同时除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到费马小定理。
3.费马小定理的应用***
费马小定理可以快速求得x关于p的逆元（参看上面逆元的概念）。
前提当然得是x与p互质才有逆元。
即：x*x^p-2 ≡ 1 （mod p）
所以x^p-2就是x关于p的逆元。
4.代码实现***
美国高防vps
这里使用了快速幂算法来求x^p-2。
#include<iostream>#define ll long longusing namespace std;ll quickpow(ll a, ll b, ll p){ ll temp = 1; while(b){ if(b & 1) temp = (temp * a) % p; a = (a * a) % p; b >>= 1; } return temp;}int main(){ll a, p;cin>>a>>p;cout<<quickpow(a, p-2, p)<<endl;return 0;} 85174493
