写这个类型博客的目的就是想总结一下某个专题的知识点，方便以后比赛前复习，由于太菜，如有错误，还请斧正。

首先%运算对于加减乘是没有影响的原先怎么做现在还是怎么做，对于除法呢影响就比较大了，这里我们必须引入一个概念——逆元，逆元其实和倒数差不多，比如a/b对p取模就等于a先对p取模再乘上b基于p的逆元

一般来说求逆元有三种解法

以下参考https://blog.csdn.net/forever_dreams/article/details/82533362

1.费马小定理

int Quick_Power(int a,int b,int c)
{
	int ans=1;
	while(b)
	{
		if(b&1)
		  ans=(1ll*ans*a)%c;
		a=(1ll*a*a)%c;
		b>>=1;
	}
	return ans;
}
int main()
{
	int a,b,p;
	scanf("%d%d%d",&a,&b,&p);
	b=Quick_Power(b,p-2,p);
	printf("%d",((a%p)*(b%p))%p);
	return 0;
}

2.扩展欧几里得定理

void exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int main()
{
	int a,b,p,x,y;
	scanf("%d%d%d",&a,&b,&p);
	exgcd(b,p,x,y);
	x=(x+p)%p;
	printf("%d",((a%p)*(x%p))%p);
	return 0;
}

3.线性筛

int inv[N];
void get_inverse(int n,int p)
{
	int i;
	inv[1]=1;
	for(i=2;i<=n;++i)
	  inv[i]=(p-p/i)*inv[p%i]%p;
}
int main()
{
	int n,i,p;
	scanf("%d%d",&n,&p);
	get_inverse(n,p);
	return 0;
}

当然除了加减乘除这些基本运算以外还有许多地方要用到%

快数幂：

typedef long long ll
ll ppow(ll a, ll b, ll m){
	ll ans = 1;
	while(b > 0){
		if(b & 1){
			ans = ans * a % m;
		}
		a = a * a % m;
		b >>= 1; 
	} 
	return ans;
}

快数乘

这个比较常用是O（logn）

ll ksc(ll x,ll y,ll p){
    ll res=0;
    while(y){
        if(y&1)res=(res+x)%p;
        x=(x<<1)%p; y>>=1;
    }return res;
}

这还有O1的（刚刚查到的，没用过）

ll ksc(ll x,ll y,ll p){
    ll z=(ld)x/p*y;
    ll res=(ull)x*y-(ull)z*p;
    return (res+p)%p;
}

最后讲一下负数取模

一般来说负数直接取模会出错（本人接连在这跌倒两次），因此我们只需要将取模操作手动完成就行了

if(a<=-mod)
{
	k=a/(-mod);
	a+=k*mod;
}