初级数论

目录

  • GCD & LCM
  • 欧拉函数
  • BSGS 算法
  • CRT 中国剩余定理
  • 原根

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} \]

算法步骤

  1. 计算这些模数的积,记为\(b=\prod^n_{i=1} p_i\)。
  2. 遍历每一个同余方程\(i\)
    1. 计算\(m=\frac{b}{p_i}\)。
    2. 计算\(m^{-1}\; (\mod \; p_i)\)
    3. 计算\(c_i = \sum m \times m^{-1}\)
  3. 答案\(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) \)即可。

发布者

Kal0rona

江西师大附中全机房最弱

《初级数论》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注