同余与模运算

模运算：

(a+b)modn = ((amodn)+(bmodn))modn

(a-b)modn = ((amodn)-(bmodn)+n)modn

(a*b)modn = ((amodn)*(bmodn))modn

int mul_mod(int a,int b,int n)
{
    a%=n;  b%=n;
    return (int)((long long) a*b % n);
}

例1：大整数取模nmodm，你<10^100,m<10^9

1234 = ((1*10+2)*10+3)*10+4;

依次取模即可

1 int ans = 0;
2 for(int i=0;i<len;i++)
3 {
4     ans = ((long long)ans*10 +ｎ[i])%m;
5 }

例2幂取模

快速幂

1 int pow_mod(int p,int n,int m)
2 {
3     if(n==1)
4         return p;
5     int x=pow_mod(p,n/2,m);
6     long long ans = (long long)x*x%m;
7     if(n%2)ans*=p;
8     return (int)(ans % m);
9 }

例3：模线性方程

输入a,b,n,解方程组a*x≡b(modn)a,b,n<10^9

对于同余符号，可以这么理解，就是a*x = y1*n+K

b =y2*n+K;

所以ax-b = (y1-y2)*n。令其为ax-b = y*n,方程转化为ax-ny=b，也就是求线性方程的一个x的解

由欧几里得公式，如果b%gcd（a，n）=0时方程有解，否则无解

同余与模运算

推荐阅读