一些比较基础的数论知识的学习笔记

数论

---

最近开始系统的学习 OI 中必不可少的数论知识（对我之前只会 exgcd

感觉很有必要做个笔记

这里面放的都是些比较基础的知识和证明

高深的东西我可能会另外开坑

就酱

长期不定期更新 弃坑

---

线性筛

线性筛算法中的每个合数都只会被其最小的质因子（也可以说是最大的因子）筛去，所以复杂度是 $O(N)$ 的。

过程大概就是枚举那每一个最大的因子与最小的质因子，需要注意的是如果那个最小的质因子是另一个枚举的因子的质因数，那么后面的质因子就应不再枚举，这里令素数表为 $Prime$ 。

如果 $Prime_i | x$，那么 $Prime_{i+1} * x$ 的最小质因子就是 $Prime_i$ ，$Prime_{i+2}, Prime_{i+3}$ 及后面的质数也一样，如果这时不退出的话一些数就会被重复筛去。

下面线性筛模板用来 AC Luogu3383

#include <iostream>
#include <cstdio>
const int MAXN = 1e7 + 5;
int N, M, Tot;
int Prime[700000];
bool A[MAXN];
int main()
{
    scanf("%d %d", &N, &M);
    A[0] = A[1] = 1;
    for(int i = 2; i <= N; ++i)
    {
        if(!A[i]) Prime[++Tot] = i;
        for(int j = 1; j <= Tot && i * Prime[j] <= N; ++j)
        {
            A[i * Prime[j]] = 1;
            if(i % Prime[j] == 0) break;
        }
    }
    while(M--)
    {
        int q = read(); 
        if(A[q]) puts("No");
        else puts("Yes");
    }
    return 0;
}

POJ2689 Prime Distance

算术基本定理

任意一个大于 $1$ 的整数 $N$ 都能分解为几个质数之积，就像下面这个形式

$$N = \prod a_{k}^{b_{k}}$$
因为这个分解是惟一的，所以这个定理又叫”唯一分解定理“。

为什么是唯一的呢？因为如果任意一个 $b_k$ 减一，那就需要再补一个 $a_k$ 的因子，然而 $\{a\}$ 都是质数，所以分解唯一。

代码就是分解质因数。。。

之前说了线性筛能够保证用每一个数最小的质因子来筛去某一个数，其实就是可以 $O(n)$ 求出每个数最小的质因子，那么就可以用来加速质因数分解。前几天打 cf 的时候遇到了这样的一道题。。。

因为懒癌，我就不贴线性筛加速的代码了

#include <iostream>
#include <cstdio>
#include <cmath>
const int MAXN = 1000 + 5;
int N, Tot;
int A[MAXN], B[MAXN];
int main()
{
    scanf("%d", &N);
    for(int i = 2; i <= std::sqrt(N); ++i)
    {
        if(N % i == 0) 
        {
            A[++Tot] = i;
            while(N % i == 0)
            {   
                N /= i;
                ++B[Tot];   
            }
            if(N == 1) break;
        }
    }
    if(N > 1)
    { 
        A[++Tot] = N;
        B[Tot] = 1;
    }
    for(int i = 1; i <= Tot; ++i) printf("%d %d\n", A[i], B[i]);
    return 0;
}

然后写一些算术基本定理的推论

$N$ 的正约数个数为 $\prod (b_k+1)$

$N$ 的所有正约数之和为 $\prod(\sum_{i=0}^{b_k} a_k^i)$

这两个式子都比较显然，就不写证明了。

欧几里得算法

$$gcd(a,b)=gcd(b,a \ mod \ b)$$

这个没啥好讲的，但我还是要证明一下。

令 $\lfloor \frac{a}{b} \rfloor$ 为 $p$ ，$a \ mod \ b$ 为 $r$，$a=pb+r$ 。对于 $a, b$ 任意公因数 $d$ ，$d | a$ ，$d | pb$， 那么 $d|(a-pb)$ ，也就是 $d|(a \ mod \ b)$，所以 $a,b$ 的公因数集合与 $b, a \ mod \ b$ 的公因数集合相同。

#include <cstdio>
int gcd(int a, int b)
{
    if(b == 0) return a;
    else return gcd(b, a % b);
}
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", gcd(a, b)); 
    return 0;
}

这个算法是 $O(\log(a+b))$ 的，下面讲下更相减损术。

更相减损术

这个算法来自《九章算数》，它原本是为约分而设计的，但适用于任何求最大公因数的问题。

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

请自行翻译

大概就是有两个式子

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

这里默认 $a \geq b$

因为对于 $a,b$ 的任意公因数 $d$ ，$d|(a-b)$，所以上式得证。

还有 $gcd(a,b)*2=gcd(2a,2b)$ ，这个式子显然成立。

在高精度下求 gcd 可考虑用更相减损术代替欧几里得。

#include <cstdio>
#include <algorithm>
int gcd(int a, int b)
{
    if(a < b) std::swap(a, b);
    if(b == 0) return a;
    if(a & 1 == 0 && b & 1 == 0) return gcd(a >> 1, b >> 1) << 1;
    return gcd(b, a - b); 
}
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", gcd(a, b)); 
    return 0;
}

Stein 算法

其实更相减损术很像这个 Stein 算法

众所周知，欧几里得算法求 gcd 很♂快

但是在算大整数的时候，需要试商，就会变慢。Stein 算法很好的解决了这个问题。

如果 $a,b$ 中有一个奇数，那我们就可以将另一个数中的质因子 $2$ 全部约去，因为这个时候两数的 gcd 不可能是 $2$ 的倍数。

剩下的就和更相减损术差不多。

#include <cstdio>
#include <algorithm>
int stein(int a, int b)
{
    if(a == 0) return b;
    if(b == 0) return a;
    if(a & 1 == 0 && b & 1 == 0) return stein(a >> 1, b >> 1) << 1;
    if(a & 1 == 0) return stein(a >> 1, b);
    if(b & 1 == 0) return stein(a, b >> 1);
    if(a > b) return stein(b, a - b);
    else return stein(a, b - a);
}
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", stein(a, b)); 
    return 0;
}

欧拉函数

$\varphi(N)$ 欧拉函数等于 $\sum_{i=1}^N [gcd(N,i)=1]$。也就是与 $N$ 互质的数的个数。

算数基本定理有 $N = \prod a_{k}^{b_{k}}$ ，那么 $\varphi(N) = N*\prod_{质数k|N} (1-\frac{1}{k})$。

大概证明一下
$N$ 的质因子 $p$ 会在与 $N$ 互质的数集合中筛去 $\frac{N}{p}$ 个数，质因子 $r$ 同理。因为一个数的质因子不会大于 $\sqrt{N}$ ，所以 $p*r$ 一定小于 $N$ ，那么在 $1-N$ 中，$pr$ 的倍数就会被筛去两次，所以容斥一下，答案加上 $\frac{N}{pr}$ 。
$N - \frac{N}{p} - \frac{N}{r} + \frac{N}{pr}$ 化简可得 $N(1-\frac{1}{p})(1-\frac{1}{r})$ 。

分解 $N$ 的质因数时可以求出 $\varphi(N)$ 。

#include <cstdio>
#include <cmath>
int N;
inline int Phi()
{
    int res = N;
    for(int i = 2; i <= sqrt(N); ++i)
    {
        if(N % i == 0)
        {
            res = res / i * (i - 1);
            while(N % i == 0) N /= i;
        }
    }
    if(N > 1) res = res / N * (N - 1);
    return res;
}
int main()
{
    scanf("%d", &N);
    printf("%d\n", Phi());
    return 0;
}

51NOD1040 最大公约数之和

然后有个性质

• $1$ 到 $N$ 中与 $N$ 互质的数的和为 $\frac{N}{2}*\varphi(N)$ 。
• 若 $a,b$ 互质，则 $\varphi(a,b)=\varphi(a) \varphi(b)$ 。
• 唯一分解定理有 $N=\prod a_k^{b_k}$，那么 $\varphi(N)=\prod \varphi(a_k^{b_k})$ 。
• 当 $p$ 是质数时，如果 $p \mid i$ ，$\varphi(p*i)=p*\varphi(i)$，否则 $\varphi(p*i)=(p-1)*\varphi(i)$ 。

那么就可以线性筛出 $1$ 到 $N$ 内的 $\varphi(i)$ 。

#include <iostream>
#include <cstdio>
const int MAXN = 1e5 + 5;
int N, Tot;
int Prime[MAXN], Phi[MAXN];
bool A[MAXN];
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
void EulerSieve()
{
    Phi[1] = 1;
    for(int i = 2; i <= N; ++i)
    {
        if(!A[i])
        {
            Prime[++Tot] = i;
            Phi[i] = i - 1;
        }
        for(int j = 1; j <= Tot && i * Prime[j] <= N; ++j)
        {
            A[i * Prime[j]] = 1;
            if(i % Prime[j] == 0)
            {
                Phi[i * Prime[j]] = Phi[i] * Prime[j];
                break;
            }
            else Phi[i * Prime[j]] = Phi[i] * (Prime[j] - 1);
        }
    }
}
int main()
{
    N = read();
    EulerSieve();
    for(int i = 1; i <= N; ++i) printf("Phi(%d)=%d\n", i, Phi[i]);
    return 0;
}

欧拉定理

如果正整数 $a,b$ 互质，就有 $a^{\varphi(b)}≡1\pmod b$ 。

我不会证。

推论：$a^b≡a^{b\ \ mod \ \ \varphi(b)}\pmod b$

费马小定理

若 $p$ 为素数，有 $a^p≡a\pmod p$ 。

其实就是欧拉定理中的 $b$ 为素数时两边乘个 $a$ 的结果。

那么只要会证欧拉定理就会证这个了

所以我不会证

拓展欧几里得

不写了。。。

　一堆同y

乘法逆元

我们都知道加减乘法都是满足同余性的。。。但除法就不一定了

现在就是要求出一个正整数 $x$ ，使得 $\frac{a}{b}≡ax\pmod p$。

注意 $x$ 只有当 $b,p$ 互质的时候才会存在

现在记 $x$ 为 $b^{-1}$

将这个式子化简，得到 $b*b^{-1}≡1 \pmod p$ 。当 $p$ 为质数的时候，直接上费马小定理。当 $p$ 与 $b$ 互质的时候，也可以使用 exgcd 来解同余方程。

前面也都说了费马小定理就是欧拉定理的一个子集对不对。。。

所以当 $p$ 不是质数但与 $n$ 互质的时候，除了 exgcd，也可以用欧拉定理来求逆元。

$b^{\varphi(p)-1} \pmod p$ 就是逆元

还是懒癌，这里只有费马小定理的代码。。。

还有一种线性递推逆元的算法

快速幂（费马小定理）

#include <iostream>
#include <cstdio>
typedef long long LL;
#define int LL
int N, P;
inline int Fpow(int x, int y)
{
    int r = 1, base = x;
    while(y)
    {
        if(y & 1) r = (r * base) % P;
        base = (base * base) % P;
        y >>= 1;
    }
    return r % P;
}
signed main()
{
    scanf("%lld %lld", &N, &P);
    for(int i = 1; i <= N; ++i) printf("%lld\n", Fpow(i, P - 2));
    return 0;
}

拓展欧几里得

#include <iostream>
#include <cstdio>
typedef long long LL;
#define int LL
int N, P, X, Y;
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
void exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    int t = y;
    y = x - (a / b) * y;
    x = t;
}
signed main()
{
    N = read();
    P = read();
    for(int i = 1; i <= N; ++i)
    {
        exgcd(i, P, X, Y);
        while(X < 0) X += P;
        printf("%lld\n", X); 
    }
    return 0;
}

待更新。