乘法逆元以及在取模意义下的各种骚操作

乘法逆元以及在取模意义下的各种骚操作

众所周知，(a+b)%p=(a%p+b%p)%p
(a * b)%p=(a%p * b%p)%p,在a,b均为整数的情况下成立
但是，(a / b)%p!=(a%p / b%p)%p
但是a,b有可能很大导致不能直接用int或long long来表示，那么我们就要用到一个东西叫乘法逆元：
逆元的定义可能很多人看不太懂，但是乘法逆元的定义还是很简单的：
(a * b)%p==1，那么b就是a在模p意义下的乘法逆元
这个东西有什么用呢，这么解释吧，就是a^-1对p取模的值就是b
至于为什么······[a * (a^-1)]%p=1%p=1,a * b%p=1，你看这个是不是简单明了？
回归原式，(a/b)%p=(a*b^-1)%p，这不就转换成乘法了吗，那么我们就需要求出a%p和b^-1%p，前一个直接取模，后一个计算b的乘法逆元即可
计算乘法逆元有三种方法：
1、费马小定理法
费马小定理：a^n-1%n=1，a,n互质。那么a * a^n-2%n=1
所以，a在模n意义下的逆元就是a^n-2，用快速幂计算比较快，但是这个方法仅适用于p是质数的情况下
代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int a,b;
int c;
inline ll quickmi(ll x)
{x%=b;ll ans=1;while(c){if(c&1)ans=ans*x%b;x=x*x%b;c>>=1;}c=b-2;return ans%b;
}
inline void write(ll x)