lanqiaoOJ 4185：费马小定理求逆元

【题目来源】
https://www.lanqiao.cn/problems/4185/learning/

【题目描述】
给出 n，p，求 。其中， 指存在某个整数 0≤a<p，使得 na mod p=1，此时称 a 为 n 的逆元，即 。数据保证 p 是质数且 n mod p≠0。

【输入格式】
输入包含一行，为两个整数 n，p。

【输出格式】
输出包括一行，为一个整数，表示 。

【输入样例】
3 5

【输出样例】
2

【说明】
3×2 mod 5=1，所以 。

【评测数据规模】
对于100%的评测数据，1≤n, p≤10^9+7

【算法分析】

此题通过分析可以知道就是求nx≡1（mod p）

注意：题目中的 表示 n 的逆元，是一个表示符号，而不是数学中的n的1次方的倒数

因为题目中p为素数，所以可以使用费马小定理

【Code】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;LL fastPow(LL a,LL n,LL p) {LL ans=1;while(n) {if(n & 1) ans=ans*a%p;n>>=1;a=a*a%p;}return ans%p;
}int main() {LL n,p;cin>>n>>p;cout<<fastPow(n,p-2,p);return 0;
}