• 近日自行补习了数论相关的知识,觉得又是一个蛮有趣的世界,特在此开坑。

一、整数与余数

1.整数的离散性:x < y <==> x+1<=y ; x,y为整数
2.整数的奇偶性:
(1)奇±奇=偶 偶±偶=偶 奇±偶=奇 偶 * 偶=偶 奇 * 偶=偶 奇 * 奇=奇
(2)奇^2=8m+1 偶^2=8m or 8m+4; m为整数
(3)正整数n,n=2^m*l, m为非负整数,l为奇数
先写这些。。。

二、带余除法

a, b为整数,b>0,则存在整数q,r,使得a=bq+r,其中,0<=r<=b,且q,r由上述条件唯一确定。
例如:5 / 4 = 1 …… 1; -1 / 5 = -1 …… 4
可以理解为a是被除数,b是除数,q是商,r是余数。

三、同余

设m是一个给定的正整数,如果两个整数a,b用m除所得的余数相同,则称a,b对模m同余, 记为a ≡ b (mod m)。
同余的基本性质:
1.若a≡0(mod m),则a|m;
2.反身性:a≡a (mod m);
3.对称性:若a≡b(mod m),则b≡a (mod m);
4.传递性:若a≡b(mod m),b≡c(mod m),则a≡c(mod m);
5.同余式相加:若a≡b(mod m),c≡d(mod m),则a+c≡b+d(mod m);
6.同余式相乘:若a≡b(mod m),c≡d(mod m),则ac≡bd(mod m)。
7.线性运算:如果a ≡ b (mod m),c ≡ d (mod m),那么
(1)a ± c ≡ b ± d (mod m);
(2)a * c ≡ b * d (mod m)。
8.除法:若ac ≡ bc (mod m),c≠0,则a ≡ b (mod m/gcd(c,m)),其中gcd(c,m)表示c和m的最大公约数,特殊地,gcd(c, m)=1,则a ≡ b (mod m);
9.幂运算:如果a≡b(mod m),那么
10.若a ≡ b (mod m),n=m,则a ≡ b (mod n);
11.若a≡b(mod mi),(i=1,2,3,……,n),则a≡b(mod lcm[m1,m1,……,mn])。

由此延伸出算法快速幂求模:

int ksm(int a, int b, int c)
{
    a %= c;
    int ans = 1;
    while(b != 0)
    {
        if(b & 1) ans = (ans*a) % c;
        b >>= 1;
        a = (a*a) % c;
    }
    return ans;
}

先到这里。