数论

质数

欧拉线性筛

void get_prime(int n)
{
    int prime[n];
    bool num[N];
    int cnt = 0
    for(int i = 1;i <= n;i ++) num[i] = i;

    for(int i = 2;i <= n;i ++)
    {
        if(!num[i]) prime[++ cnt] = i;

        for(int j = 1;j <= cnt && i * prime[j] <= n;j ++)
        {
            num[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

约数

算术基本定理

解释一下正约数的个数问题：其实本质上是一个乘法原理，对于每一个质数\(p\)而言，有\(c_i + 1\)种选择的方案.
即从\(0到c_i\)。

N的正约数的和为

求N的正约数集合（试除法）

void get_factor(int n)
{
    int factor[sqrt(n)],cnt = 0;
    for(int i = 1;i * i <= n;i ++)
    {
        if(n % i == 0)
        {
            factor[++ m] = i;
            if(n / i != i)
                factor[++ m] = n / i;
        }
    }
}

求1到n每个数的正约数集合——倍数法

vector<int > factor[500010];
for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n / i;j ++)
            factor[i * j].push_back(i);

互质与欧拉函数

1~N中与N互质的数的个数叫做欧拉函数

求一个数的欧拉函数值：

int euler(int n)
{
    int ans = n;
    for(int i = 2;i * i <= n;i ++)
    {
        if(n % i == 0)
        {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

性质

1.任意n > 1,1~n中与n互质的数之和为\(n * \varphi (n) / 2\)

2.若\(a,b互质，则\varphi(ab) = \varphi(a)*\varphi(b)\)

3.设p为质数，若p能被n整除，且\(p^2\)能被n整除，则\(\varphi(n) = \varphi(n / p)*p\)

4.设p为质数，若p能被n整除，但\(p^2\)不能被n整除，则\(\varphi(n) = \varphi(n / p) * (p - 1)\)

5.\(\sum_{d|n} \varphi(d) = n\)

求1~n的数的欧拉函数值

void get_euler(int n)
{
    int v[n]={0},prime[n],phi[n];
    int cnt = 0;
    for(int i = 2;i <= n;i ++)
    {
        if(v[i] == 0) 
        {
            v[i] = i;
            prime[++ cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= m && i * prime[j] <= n;j ++)
        {
            v[i * prime[j]] = prime[j];
            phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] : prime[j] - 1);
            if(i % prime[j] == 0)break;
        }
    }

}

同余

定义

若整数a和整数b除以正整数m所得到的余数相等，则称a，b同余.

同余类与剩余类

对于任意a属于[0,m - 1],集合 {a + km}(k 属于 Z)的所有数mod m同余，余数都是a，称该集合是一个模m的同余类。

模m的同余类一共有m个,它们构成m的完全剩余系

1~m中与m互质的数代表的同余类共有\(\varphi(m)\)个,构成简化剩余系.

性质:

1.\(m | a - b \Leftrightarrow a \equiv b ( \mod m)\)

\(因为a,b对于m的余数相等,所以很容易证明,a - b 是能够被m整除的\)

（这个性质多用于之后证明两个数是否同余）

若\(a_1 \equiv b_1(\mod m),a_2 \equiv b_2(\mod m)\)

那么存在以下性质：

2.\(a_1 \pm a_1 \equiv b_1 \pm b_1 (\mod m)\)

证明：

3.\(a_1a_2 \equiv b_1b_2(\mod m)\)

证明：

4.\(a_1^k \equiv b_1^k(\mod m)\)

这个式子是性质三特例的变形。

费马小定理

若p是质数，则对于任意整数a，有

证明：

欧拉定理

欧拉定理的推论

特别的，当a和n不一定互质时且b > \(\varphi (n)\) 时，有\(a^{b} \equiv a^{b \mod \varphi(n) + \varphi(n)}\)

欧几里得算法扩展

bezout定理

\(对于ax +by = c，如果gcd（a,b）|c,那么有解，反之无解\)

直接上代码le:

int exgcd(int a,int b,int &x,int &y)
{
    if(b == 0) {x = 1;y = 0;return a;}
    int d = exgcd(b,a % b,x,y);
    int z = x;x = y;y = z - y * (a / b);
    return d;
}

这份代码最后返回值为\(gcd(a,b)\) ，因为x，y是引用的，所以其值会改变。

利用上述代码可以找出一组特解，然后可以得出通解：

乘法逆元

对与一个整数a，有a*x\(\equiv\) 1(\(\mod p\)),那么整数x为a的模乘法逆元。

一个数a有逆元的充分必要条件是gcd（a，p） = 1；

特别的，当p和a互质的时候，由费马小定理得知：\(a * a^{p - 2}\equiv 1(\mod p)\)

也就是说，a，p互质时，\(a^{p - 2}\)为a的模乘法逆元

线性同余方程

\(ax \equiv b(\mod m) 推出（反推出） m|ax - b 推出（反推出）存在整数y，使得ax + my = b\)

有解：参考上文解不定方程。

所以计算时先用欧几里得算法求出\(x_0,y_0\)满足\(ax_0 + my_0 = gcd(a,m)\)

\(x = x_0 * b / gcd(a,m)\)就是原方程的一组特解.

方程的通解:\(X = x \% (m/gcd(a,m)) + k(m/gcd(a,m)) (k属于整数)\)

中国剩余定理

代码：

typedef long long LL;
void get_factor()
{
    LL n ,a ,m;
    LL x0 = 0,m0 = 1,x,y;\\x0代表当前积累下来的候选答案，m0代表积累下来的最小公倍数
    for(LL i = 1;i <= n;i ++)
    {
        cin >> m >> a;\\输入第i个a和m的值
        LL d = exgcd(m0,m,x,y);\\欧几里得算法求解
        if((a - x0) % d != 0)\\如果a-x0不是d的倍数
        {
            puts("-1");return 0;\\输出无解
        }
        LL k = (a - x0) / d * x;\\k为原方程的一个特解
        k = (k % m + m) % m;\\将k进行缩小
        x0 = x0 + k * m0;\\更新积累的解的值
        m0 = m0 / d * m;\\更新积累的m0的值
        x0 = (x0 % m0 + m0) % m0;\\将x0进行缩小
    }
    cout << x0 << endl;
}

BSGS算法

\(问题:给定整数a,b,p,其中p为质数,求一个非负整数x,使得a^x\equiv b(\mod p)\)

int power(int a,int n,int p)
{
    if(n == 1) return a % p;
    int t = power(a ,n / 2,p);
    if(n % 2) return (((long long)t * t) % p * (a % p)) % p;
    return (long long)t * t % p
}
int baby_step_giant_step(int a,int b,int p)
{
    map<int ,int >hash;
    hash.clear();
    b %= p;
    int t = int (sqrt(p)) + 1;
    for(int j = 0;j < t;j ++)
    {
        int val = (long long)b * power(a,j,p) % p;
        hash[val] = j;
    }
    a = power(a,t,p);
    if(a == 0) return b == 0 ? 1 : -1;
    for(int i = 0;i <= t;i ++)
    {
        int val = power(a,i,p);
        int j = hash.find(val) == hash.end() ? -1 : hash[val];
        if(j >= 0 && i * t - j >= 0) return i * t - j;        
    }
    return -1;
}

矩阵乘法

矩阵乘法

应用：可以将原题构建成为一个向量数组（大概就是如果说ｃ　＝　ａ　＋　ｂ　的话，那么ｃ　＝　ａ　＊　ｘ　＋　ｂ　＊　ｙ）两个向量相加，实际上是由这两个向量能够构成单位向量，来组成另外一个向量．挺抽象的，表述能力有限．

这个构建的模型要能够抽象为一维的（如果是二维比如ｎ　＊　ｍ的话就拉开使数组变成１　＊　ｎｍ），并且在单位时间内最多发生一次变化．

变化的形式是向量加法，或者常数相乘．

如果需要加速的话，那么还要要求递推式不变，并且向量长度ｌｅｎｔｈ不大．

高斯消元与线性空间

高斯消元

步骤:将原来的M个N元一次方程写为M行N + 1列的矩阵,最后一列为所等于的常数.

然后进行以下步骤:
1.用一个非零的数乘以某一行

2.把其中一行的若干倍加到另一行.

3.交换两行的位置

最后通过初等行变换将增广矩阵变为简化阶梯矩阵的线性方程组求解算法就是高斯消元算法

贴一份模板代码:

洛谷原题: 高斯消元

代码:

#include<bits/stdc++.h>
using namespace std;
int n;
double a[110][110];
double b[110];
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
            scanf("%lf", & a[i][j]);
        scanf("%lf", &b[i]);
    }

    for(int i = 1;i <= n;i ++)
    {
        for(int j = i;j <= n;j ++)
        {
            if(fabs(a[j][i]) > 1e-8)
            {
                for(int k = 1;k <= n;k ++) swap(a[i][k],a[j][k]);
                swap(b[i],b[j]);
                break;
            }
        }
        if(fabs(a[i][i]) < 1e-8) 
        {
            puts("No Solution");
            return 0;
        }
        for(int j = 1;j <= n;j ++)
        {
            if(i == j) continue;
            double rate = a[j][i] / a[i][i];
            for(int k = 1;k <= n;k ++)
                a[j][k] -= a[i][k] * rate;
            b[j] -= b[i] * rate;
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        printf("%.2lf\n",b[i] / a[i][i]);
    }
    return 0;
}

组合计数

\(A^m_n = n!/(n - m)!\)

二项式定理

多重集