取模,变小
(这里减法取模和除法取模需要特别注意)
1.加法取模: (A + B)% P = (A % P + B % P) % P;
2.乘法取模: (A * B) % P = (A % P * B % P) % P;
3.减法取模: (A - B)% P = (A % P - B % P + P ) % P (要加上P);
4.整除取模: (A / B)% P = (A % P * B ^ (P - 2) % P) %P);
快乘模板 : a * b % mod 当 a 和 b 很大,超出了longlong 的范围的时候,解决的方式是,使用快乘模板
//求得 a ^ b % c 的值
int multiMod(int a, int b, int c)
{
int ans = 0;//注意初始化是0,不是1
while (b)
{
if (b & 1)
ans=(ans+a)%c;
a = (a + a) % c;//和快速幂一样,只不过这里是加
b >>= 1;
}
return ans;
}
快速幂模板(使用的较多, 时间复杂度是O(logn),朴素的写法复杂度是 O(n))
模板:
//a ^ b % c
LL poww(LL a, LL b, LL c)
{
LL ans = 1; //其一与快乘不一样的地方
a = a % c;
while(b>0)
{
if(b % 2 == 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c; //其二与快乘不一样的地方
}
return ans;
}
标签:取模,int,LL,ans,快速,复杂度,模板
From: https://www.cnblogs.com/luoyefenglin/p/16843528.html