Hexo
0%

10-取模

发表于 更新于

取模

在加减乘除运算结果后，因为最终可能超出数据的表达范围，所以需要进行取模操作，但是有可能在运算中途就已经超出了范围，所以要进行一些运算上的优化

(0)先验

  1. 常见的mod有1e9+7、41、13331、2147483647
  2. cpp的int目前是4B，即范围是-2147483648~2147483647，为了防止mod的值过大，所以采用保险的long long类型
  3. 下面代码都是经过typedef long long ll

(1)加法ADD

1
2
3
4
ll add_mod(ll a,ll b,ll mod)
{
    return (a%mod+b%mod)%mod;
}

(2)减法SUB

1
2
3
4
ll sub_mod(ll a,ll b,ll mod)
{
    return (a%mod-b%mod+mod)%mod;
}

(3)乘法MUL

1
2
3
4
ll mul_mod(ll a,ll b,ll mod)
{
    return (a%mod)*(b%mod)%mod;
}

(4)除法DIV

除法需要用到乘法逆元、费马小定理等数学知识，个人在这里直接用结论了

在次方则需要用到快速幂板子，不然会overflow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
long long quick_pow2_2(ll a,ll n,ll mod)
{
    if (a==0)
        return 0;
    a%=mod;
    long long ans=1;
    while (n!=0)
    {
        if ((n&1)==1)
        {
            ans*=a;
            ans%=mod;
        }
        a*=a;
        a%=mod;
        n>>=1;
    }
    return ans;
}
ll div_mod(ll a,ll b,ll mod)
{
    //mod必须为质数
    return (a%mod)*quick_pow2_2(b,mod-2,mod)%mod;
}

(5)完整板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#ifndef CONGRUENCE
#define CONGRUENCE

typedef long long ll;

/*
 * 操作a与b，且结果对mod求余
 * add : (a+b)%mod = (a%mod+b%mod)%mod
 * sub : (a-b)%mod = (a%mod-b%mod+mod)%mod
 * mul : (a*b)%mod = (a%mod)*(b%mod)%mod
 * div : (a/b)%mod = a*(b^(-1))%mod
   若mod为一个质数，则有 x^(-1)%mod=x^(mod-2)%mod，次方操作需要采用快速幂
   div ：(a/b)%mod = (a%mod)*(b^(mod-2)%mod)%mod
 */

long long quick_pow2_2(ll a,ll n,ll mod)
{
    if (a==0)
        return 0;
    a%=mod;
    long long ans=1;
    while (n!=0)
    {
        if ((n&1)==1)
        {
            ans*=a;
            ans%=mod;
        }
        a*=a;
        a%=mod;
        n>>=1;
    }
    return ans;
}

ll add_mod(ll a,ll b,ll mod)
{
    return (a%mod+b%mod)%mod;
}

ll sub_mod(ll a,ll b,ll mod)
{
    return (a%mod-b%mod+mod)%mod;
}

ll mul_mod(ll a,ll b,ll mod)
{
    return (a%mod)*(b%mod)%mod;
}

ll div_mod(ll a,ll b,ll mod)
{
    //mod必须为质数
    return (a%mod)*quick_pow2_2(b,mod-2,mod)%mod;
}
#endif