Chapter 1

数论

1.1 埃氏筛

遇到一个数$x$,$x$的所有倍数一定是合数,可以避免很多次无用检测。从小到大这样运行一次最后没有标记的就是素数。$O(n loglogn)$。

int Eratosthenes(int n)
{
    int cnt = 0;
    not_prime[0] = not_prime[1] = 1;
    for (int i = 2; i * i <= n; ++i)
    {
        if (!not_prime[i])
        {
            prime[cnt++] = i;
            for (int j = i * i; j <= n; j += i)// 2到i-1的倍数筛过了
                not_prime[j] = 1;  // 是i的倍数的均不是素数
        }
    }
    return cnt;
}

1.2 欧拉筛

埃氏筛会将一个合数重复多次标记。让每个合数都只被标记一次,可以降低时间复杂度到$O(n)$。

int Euler(int n)
{
    int cnt = 0;
    for (int i = 2; i < n; ++i)
    {
        if (!not_prime[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt && i * prime[j] >= n; ++j)
        {//这里不是用i的倍数来消去合数,而是把 prime里面纪录的素数,升序来当做要消去合数的最小素因子。
            not_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;// i被pri[j]筛过,i*其他数一定是pri[j]的倍数,也被筛过
        }
    }
    return cnt;
}

1.3 gcd 与 lcm

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

1.4 Exgcd

ll Exgcd(ll a, ll b, ll& x, ll& y)
{
    if (!b) { x = 1; y = 0; return a; }
    ll d = Exgcd(b, a % b, x, y);
    ll t = x, x = y, y = t - (a / b) * y;
    return d;
}

1.5 快速幂

ll q_pow(ll a, ll b, ll m)
{// a ^ b mod m
    a = a % m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

1.6 乘法取模(快速乘)

ll mul_mod(ll a, ll b, ll m)
{// a * b mod m, a * b爆炸, m在long long范围内时。
    ull c = (ull)a * b - (ull)((long double)a / m * b + 0.5L) * m;
    return (c + m) % m;
}

1.7 逆元

如果一个线性同余方程 $ax\equiv 1(mod~b)$ ,则 $x$ 称为 $ax~mod~b $ 的逆元,记作 $a^{-1}$。

1.7.1 快速幂法求逆元

$ax\equiv 1~(mod~b)$,$ax\equiv a^{b-1}~(mod~b)$,$x\equiv a^{b-2}~(mod~b)$。(费马小定理)

故求 x=q_pow(a, b - 2, b) 即可,要求b是一个素数。

1.7.2 Exgcd求逆元

方程 $ax+by=1$ 与方程 $ax\equiv 1~(mod~b)$ 是等价的。

故求 exgcd(a, b, x, y) 即可,$x$ 是逆元。

要求 $x$ 是 $[0,b)$ 的数,注意以上两种方法都要用x=(x%b+b)%b约束。

1.8 线性求逆元

线性求 $1$ 到 $n$ 关于 $p$ 的逆元,$O(n)$。

inv[1] = 1;
for (int i = 2; i <= n; ++i) 
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;

线性求任意 $n$ 个数的逆元,$O(n+logp)$。

首先计算 $n$ 个数的前缀积 $s[i]$,计算 $s[n]$ 单个的逆元,记作 $sv[n]$。

显然有 $sv[i-1]=sv[i]*a[i]%p$,$inv[i]=sv[i]*s[i-1]%p$。可以计算出所有 $sv$,求得 $inv$。

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2, p);
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

1.9 费马小定理

1.9.1 费马小定理

若 $p$ 是素数,并且 $gcd(a,p)=1$,则 $a^{p-1} \equiv 1~(mod~p)$,$a^p\equiv a~(mod~p)$。

1.9.2 费马小定理逆否定理

若存在满足 $gcd(a,p)=1$ 的正整数 $a$,使得 $a^{p-1}\not \equiv 1~(mod~p)$ 成立,则 $p$ 是合数。

1.9.3 费马小定理的逆命题

若对任意满足 $gcd(a,p)=1$ 的正整数 $a$,使得 $a^{p-1} \equiv 1~(mod~p)$ 成立,则 $p$ 是素数。

此逆命题是错误的,但出错概率很小。

1.10 欧拉函数与欧拉定理

1.10.1 欧拉函数

$\varphi(n)$ 为欧拉函数,表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

  • $\varphi(1)=1$,$\varphi(n)=n-1$ ($n$为素数时)。
  • 欧拉函数时积性函数。

求欧拉函数:

ll euler_phi(ll n)
{
    ll ans = n;
    for (ll 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$ 的欧拉函数:

void pre()
{
    int cnt = 0;
    not_prime[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!not_prime[i])
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= N; j++)
        {
            not_prime[i * prime[j]] = 1;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

1.10.2 欧拉定理

若 $gcd(a,m)=1$,则 $a^{\varphi(m)}\equiv 1~(mod~m)$。

1.10.3 扩展欧拉定理

$$ a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p $$

关于

目前正在整理数论相关的模板,比较忙。
以后有时间会细分,写清楚一些(证明,推导等)。

最后修改:2022 年 04 月 13 日
如果觉得我的文章对你有用,请随意赞赏