GCD & LCM

GCD

我们记\(gcd(a,b)\)为\(a\)与\(b\)的最大公因数。\(gcd\)满足以下几条性质：

\(m*gcd(a,b)=gcd(ma,mb)\)
\(gcd(\frac{a}{c},\frac{b}{c})=\frac{gcd(a,b)}{c}\)
\(gcd(a,m)*gcd(b,m)=gcd(ab,m)\)

更相减损术

\(gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)\)

LCM

我们记\(lcm(a,b)\)为\(a\)和\(b\)的最小公倍数。\(lcm\)可以转换为\(gcd\)，所以读者可以自己尝试导出\(lcm\)的性质：

\[ a*b=gcd(a,b)*lcm(a,b) \]

欧拉函数

欧拉函数的标记为\(\varphi(x)\)，意义为在\([1,n]\)与\(n\)互质的数的个数。一般的，欧拉函数的表达式如下：

\[ \varphi(N) = N*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*\frac{p_3-1}{p_3} \dots = N*\prod_{质数p|N}(1-\frac{1}{p}) \]

接下来给出证明。

证明设\(p,q\)为\(N\)的质因子，则\(N\)内有\(\frac{N}{p}\)个\(p\)的质数，有\(\frac{N}{q}\)个\(q\)的质数。如果将它们去除，则会多去除一次\(p*q\)的共有因子，所以去掉的完整式为：

\[ N- \frac{N}{p} – \frac{N}{q} + \frac{N}{pq} \\ N*( 1 – \frac{1}{pq} – \frac{1}{p} – \frac{1}{q} ) \\ N*(1 – \frac{1}{p})(1 – \frac{1}{q}) \]

因此得证。程序设计中，直接分解质因数时计算即可。

欧拉函数的性质

- - \([1,N]\)中与\(N\)互质的数的和为\(N*\frac{\varphi(N)}{2}\)。
    证明根据更相损减数，设\(x\)为与\(N\)互质的数，即\(gcd(x,N)=1\)，也有\(gcd(N – x,N)=1\)，也就是说，互质的数是成对出现的，所以与\(N\)互质的数的平均值为\(\frac{N}{2}\)，进而得出此性质。
  - 若\(a,b\)互质，则有\(\varphi(ab)=\varphi(a)\varphi(b)\)
  - \(\sum_{i|N}\varphi(i)=N\)

欧拉定理

若\(a\)与\(n\)互质，则有\(a^{\varphi(n)} \equiv 1 (\mod n)\)；若\(a\)与\(n\)互质，则有\(a^b \equiv a^{b \mod \varphi(n)}\)。

BSGS 算法

BSGS 算法全称叫做”baby-step giant-step“算法，用于解决形如\(a^x \equiv b \; (\mod \; p)\)这样的方程。我们可以把这个方程进行拆解，我们设\(m=\lfloor \sqrt{p} \rfloor \)，则\(x=im-j, i \in [1, m], j \in [0, m] \)。这样的话，我们的方程就可以推到成：

\[ a^x \equiv b \; (\mod \; p) \\ a^{im-j} \equiv b \; (\mod \; p) \\ a^{im} \equiv a^{j} b \; (\mod \; p)\]

我们推导出来了！这个时候，我们只需要用哈希表来处理后半部分的值，把键为\(a^{j} b\)，值为\(j\)的项插入哈希表，之后再枚举前半部分，只要哈希表存在相同的项，那么我们的答案：

\[ x = im-j \\ x = im – hashTable[im] \]

就很容易求得。代码如下：

hashTable.clear();
ll m = ceil(sqrt(p));
for (int j = 0, x = 1; j <= m; j++, x = x * a % p)
    hashTable[x * b % p] = j;
ll unit = quick_power(a, m);
for (int i = 1, x = unit; i <= m; i++, x = x * unit % p)
    if (hashTable.count(x))
    {
        ans = i * m + hashTable[x];
        break;
    }

模板题；P3846:[TJOI2007]可爱的质数题解

CRT 中国剩余定理

这个算法主要是用于解同余方程组的解，结论非常的简单。我们的方程长这个样子：

\[ \begin{cases} x \equiv a_1 \; (\mod \; p_1) \\ x \equiv a_2 \; (\mod \; p_2) \\ x \equiv a_3 \; (\mod \; p_3) \\ \dots \end{cases} \]

算法步骤

计算这些模数的积，记为\(b=\prod^n_{i=1} p_i\)。
遍历每一个同余方程\(i\)
1. 计算\(m=\frac{b}{p_i}\)。
2. 计算\(m^{-1}\; (\mod \; p_i)\)
3. 计算\(c_i = \sum m \times m^{-1}\)
答案\(ans=\sum a_i*c_i \; (\mod \; m)\)。

例题：[SDOI2010]古代猪文

这道题的答案非常的显然，\(ans = G^{\sum_{N|k}C_N^{\frac{k}{N}}} \mod \; P\)。因为\(P\)是个质数，所以我们可以根据费马定理，把算式化简为：

\[ ans = G^{(\sum_{N|k} C_N^{\frac{k}{N} })mod\;(P-1)} \mod \; P \]

我们发现\(P-1\)可以分解为\(2 \times 3 \times 4679 \times 35617\)。然后我们可以用 Lucas 定理进行化简，然后列出同余方程即可（因为答案直接计算会爆掉，所以用方程来解）。

// P2480.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 500010;
const ll genP = 999911659;
ll n, g, level[MAX_N], mods[5] = {0, 2, 3, 4679, 35617}, a[5], ans;
ll quick_power(ll base, ll tim, ll p)
{
    ll tmp = 1;
    while (tim)
    {
        if (tim & 1)
            tmp = tmp * base % p;
        base = base * base % p;
        tim >>= 1;
    }
    return tmp;
}
void init(ll p)
{
    level[0] = 1;
    for (int i = 1; i <= p; i++)
        level[i] = level[i - 1] * i % p;
}
ll combine(ll n, ll m, ll p)
{
    if (m > n)
        return 0;
    return level[n] * quick_power(level[n - m], p - 2, p) * quick_power(level[m], p - 2, p) % p;
}
ll lucas(ll n, ll m, ll p)
{
    if (n < m)
        return 0;
    if (m == 0)
        return 1;
    return lucas(n / p, m / p, p) * combine(n % p, m % p, p) % p;
}
void crt()
{
    int tmp = genP - 1;
    for (int i = 1; i <= 4; i++)
        ans = (ans + a[i] * (tmp / mods[i]) % tmp * quick_power(tmp / mods[i], mods[i] - 2, mods[i])) % tmp;
}
int main()
{
    scanf("%lld%lld", &n, &g);
    if (g % genP == 0)
        printf("0"), exit(0);
    for (int k = 1; k <= 4; k++)
    {
        init(mods[k]);
        for (int i = 1; i * i <= n; i++)
            if (n % i == 0)
            {
                a[k] = (a[k] + lucas(n, i, mods[k])) % mods[k];
                if (i * i != n)
                    a[k] = (a[k] + lucas(n, n / i, mods[k])) % mods[k];
            }
    }
    crt();
    printf("%lld", quick_power(g, ans, genP));
    return 0;
}

二次剩余

问题描述

给定一个式子\(x^2 \equiv n \; (\mod \; p)\)，求\(x\)的值。其中，如果\(x\)有解，则称\(n\)为\(p\)的二次剩余。

勒让德符号

首先，我们要先判断这个方成是否有根。在这里我们引入勒让德符号来进行判断。我们定义：

\[ \left( \frac{a}{p} \right) = \begin{cases} 1, a 为 p 的二次剩余 \\ -1, a 不是 p 的二次剩余 \\ 0, a \equiv 0 \; (\mod \; p) \end{cases} \]

如何用运算来进行判别呢，接下来我们引入欧拉判别法：对于勒让德符号，有

\[ \left( \frac{a}{p} \right) = a^{\frac{p-1}{2}} \; (\mod \; p) \]

证明：分类讨论以下几种情况

当\(\left( \frac{a}{p} \right) \equiv 1 \; (\mod \; p)\)时，转化式子为\(\sqrt{ a^{p-1} } \equiv 1 \; (\mod \; p)\)，根据费马小定理，得证。
当\(\left( \frac{a}{p} \right) \equiv -1 \; (\mod \; p)\)时，二次剩余不存在。化简为\( a^{\frac{p-1}{2}} \equiv -1 \; (\mod \; p) \)，不存在二次剩余时存在\(ij \equiv a \; (\mod \; p), i != j, i, j \in [1, p-1]\)。可以知道在数论中，有一共\(\frac{p-1}{2}\)对这样的\((i,j)\)，所以勒让德式可进一步转换为\( (p-1)! \equiv -1 \; (\mod \; p) \)，根据威尔逊定理，得证。

Cipolla 算法

讲完了上面玄学判别式之后，我们来引进能计算二次剩余的 Cipolla 算法。首先，就像所有的二次方程一样，我们先需要验根，根据上面的判别法计算即可。之后，我们随机枚举一个\(c\)，满足\(c^2-n\)的勒让德符号为\(-1\)，并且设\(i=\sqrt{c^2-n}\)进行强行开根号（有点类似于虚数）。然后以下引理可以得出答案。

\[ x \equiv (n+i)^{\frac{p+1}{2}} \; (\mod \; p) \]

证明：

\[ x^2 \equiv (n+i)^{p+1} \\ \equiv (n+i)(n+i)^p \\ \equiv (n+i)(n^p+i^p) \\ \equiv (n+i)(n^p + (c^2-n)^{\frac{p-1}{2}} * i) \\ \equiv (n+i)(n^p – i) \\ \equiv (n+i)(n-i) \\ \equiv n \]

在证明中有一些简便步骤，我在这里做一个解释和证明：

\((a+b)^n \equiv \sum^n_{i=0} C_n^i a^ib^{n-i} \equiv a^n+b^n \; (\mod \; p)\)，消去中间项的原因是组合数\(C_n^i\)的存在，提供了因子\(n\)。
根据费马小定理，有\(a^p \equiv a \; (\mod \; p)\)。

积性函数

积性函数定义：如果有函数\(f(x)\)为积性函数，那么满足\(f(a)f(b)=f(ab),gcd(a,b)=1\)。欧拉函数就是一类积性函数，接下来我们来描述其性质。

积性函数的性质：

有\(n=\prod^{m}_{i=1}p_i^{c_i}\)，那么\(f(n)=\prod_{i=1}^{m}f(p_i^{c_i})\)

原根

我在这里只讲一些比较基础的东西，之后如果学到一些其他与之相关的东西我会来进行补充的。

我们在模质数\(p\)意义下，设\(g\)为\(p\)的原根，有以下性质：

\(g\)的任意次幂可以组成\(p\)的完全剩余系，也就是说，\(\{ g^k|k \in N \}\)可以看作是\([0,p-1]\)

所以我们在解题过程中，遇上\(a^b \equiv c (\mod \; p)\)且已知\(b,c,p\)的情况下求\(a\)的问题，可以把这个式子写作\(g^{tb} \equiv g^s(\mod\; p)\)，转换成解同余方程\( tb \equiv s (\mod \; p-1) \)即可。

初级数论

目录