• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021 SDSC D1 基础数论

admin

11月 28, 2021

题单中的一小部分

Part 1 初月(Easy Mode)

质数

暴力

(2) 枚举到 (⌊sqrt n⌋) 试试是否可以整除就可以啦。

显然时间复杂度是 (O(sqrt n)) 的。

埃氏筛

刚才的试除法让我们知道,找到一个数的因数是很难的。

但是找到一个数的倍数就很简单了。

因此我们可以从 ([2, n]) 中依次枚举,每个数的倍数必然不是质数
复杂度?

(F(n)=frac{n}{2}+frac{n}{3}+⋯+frac{n}{n}=O(n log n))

实际上底数是 (e),因此调和级数的常数很小,(1s) 跑得过。

由算术基本定理可知,只需要枚举质数的倍数即可。

枚举 (p) 的倍数时,只需从 (p^2) 开始枚举。

时间复杂度 (O(n log log n))

线性筛

刚才的做法已经很优秀了,可是为什么还不是线性呢?

原因仍然在于,一个数字可能被筛掉多次。

例如 (n=15),那么 (12) 这个数会在 (p=2)(p=3) 时各被筛一次。

想要做到线性,就必须让一个数只被一个质数筛掉,我们选择这个数为它最小的质因数。

首先从 (2) 到 (n) 枚举自然数 (q)(不一定是质数),再从小到大枚举比 (q) 小的质数 (p),筛掉 (pq);如果 (q)(p) 的倍数,就跳出内层循环。

void primes(int n)
{
    memset(v, 0, sizeof(v)); //清空标记数组
    m = 0;                   //质数个数
    for (int i = 2; i <= n; i++)
    {
        if (!v[i])                    //未被标记,i为质数
            v[i] = i, prime[++m] = i; //记录
        for (int j = 1; j <= m; j++)
        {
            if (prime[j] > v[i] || prime[j] > n / i)
                break;                  //i有更小的质因子,或者超出n的范围
            v[i * prime[j]] = prime[j]; //prime[j]为合数 i*prime[j]的最小质因子
        }
    }
}

根据“高斯素数定理”,如果需要粗略的估计 ([2, n]) 内的素数个数,可以直接硬点它为 (frac{n}{ln n})

GCD & LCM

GCD,Greatest Common Divisor 的缩写,意为最大公约数

LCM,Least Common Multiple 的缩写,意为最小公倍数

(gcd(a, b)=gcd(a−b, b)= gcd(b, a ext{ mod } b))

注意到每次取模至少减半,因此复杂度为 (O(log n))

而求 LCM 只需求出 GCD ,因为:

(gcd(a, b) imes ext{lcm}(a, b)=a imes b)

进制转换

(n)(a) 进制数转化为 (b) 进制数,最终为 (m) 位。

将给定的 (a) 进制数从高位向低位扫描,每次将当前结果乘以 (a),并加上当前位的系数,再从低位向高位进位即可。

复杂度 (O(nm)),用多项式科技可以优化,但大多数情况下没必要。

瓶颈在于 (n) 次乘 (a) 和进位,每次都是 (O(m)) 的。

如果 (a, b) 比较小,可以通过压位的方式进一步优化。

即,先将原数转化为 (a^p) 进制,再转化为 (b^q) 进制,可以将复杂度降为 (O(frac{nm}{pq})),为了计算方便,以 (a^p, b^q) 不超过 (2×10^9) 为妙。

Part 2 三日月(Normal Mode)

同余

若对于给定的正整数 (m),有正整数 (a, b),满足 (a=km+b, k∈Z),则称 (a, b)(m) 同余,用 (a≡b (mod m)) 表示。

(m) 意义下,整数集只剩下了 ([0, m))(m) 个整数,其他整数都应该加上或减去若干个 (m) 来调整到这个区间内。

注意到负整数 (x) 对应的数是 (km+x),而不是 (km−x)

顺便提一句,(a mod b=a−⌊frac ab⌋ imes b),这一点后面还会提到。

不难证明,模意义下的加法、减法、乘法与一般意义下相同,各运算规律依然满足。

但是很可惜,除法与它们不同。

考虑一般意义下的除法,(a÷b) 等价于 (a cdot b^{-1}),而 (b^{−1}) 满足 (bcdot b^{−1}=1) 这一性质,从而进行乘法的逆运算。

换句话说,假如我们能对任意 (b) 找到 (b^{−1}),使得(bcdot b^{−1}≡1(mod m)),不就能实现模 (m) 意义下的除法了吗?

逆元

因此,我们需要引入逆元的概念。

大多数情况下,当我们需要在模意义下做除法时,模数都是质数。

此时 ((0, m)) 中每个整数都有唯一的逆元。

inv[0] = inv[1] = 1;
for (register int i(2); i <= n; i++)
    inv[i] = (1ll * (mod - mod / i) * inv[mod % i]) % mod;

费马小定理

若整数 (a∈(0, m))(m) 为质数,则 (a^{m−1}≡1 (mod m))

有了它,我们就能求出 (a) 的逆元了:

(acdot a^{m−2}=a^{m−1}≡1 (mod m)),所以 (a^{−1}≡a^{m−2} (mod m))

绝大多数情况下逆元都是这样求的。

扩展欧几里得算法 & 裴蜀定理

(x=a^{−1}),那么有 (acdot x≡1 (mod m))

将它写成一般形式,得到 (x, y) 的不定方程 (ax−my=1)

如果能得到一组整数解 ((x_0, y_0)),我们就可以得到它的通解:

(x=x_0+km, y=y_0+ka, k∈Z),选择合适的 (k) 即可得到 (x)

现在问题在于,方程是否有解,以及如何找到一组特解。

必要性很好证明,而下面要讲的扩展欧几里得算法则通过构造证明了充分性。

(d=gcd(a, b)),扩展欧几里得算法可以给出不定方程 (ax+by=d) 的一组整数特解 ((x_0, y_0))

类比刚才的情况,通解有 (x=x_0+kcdot frac bd, y=y_0−kcdot frac ad, k∈Z)

对于 (ax+by=c, d|c) 的情况,可以先解 (ax+by=d),再将 (x, y) 都乘以 (frac cd)

考虑之前欧几里得算法求 (gcd) 的过程,我们从 (gcd(a, b)) 递归到 (gcd(b, a mod b))

(a^′=b, b^′=a mod b),那么如果我们有了不定方程 (a^′x+b^′y=d) 的一组整数解 ((x^′, y^′)),能否推出 (ax+by=d) 的一组整数解 ((x, y)) 呢?

(b^′=a mod b=a−⌊a/b⌋ cdot b),代回 (a^′x^′+b^′y^′=d) 得到 (bx^′+(a−⌊a/b⌋cdot b)y^′=d),整理得$ ay′+b(x′−⌊a/b⌋cdot y^′)=d$。

也就是说,令 (x=y^′, y=x^′−⌊a/b⌋cdot y^′) 即可完成递归的回推

裴蜀定理:对于给定的正整数 (a, b),设 (d=gcd(a, b)),则关于 (x, y) 的不定方程 (ax+by=c) 存在整数解,当且仅当 (d|c)

欧拉函数

欧拉函数:定义域为正整数的函数 (φ(x)),表示 ([1, x]) 中与 (x) 互质的正整数个数。

(x=∏p_i^{e_i}),则 (φ(x)=xcdot ∏frac{p_i−1}{p_i}),证明可以考虑每次划掉 (x) 所有质因子的倍数,剩下的就是与 (x) 互质的。

欧拉函数可以线性筛,只需判断当前质因子是否出现过,以选择乘以 (p) 还是 (p−1)


int prime[N], phi[N];
bool isprime[N];

void pre()
{
    ll cnt = 0;
    isprime[1] = 1;
    phi[1] = 1;
    for (register int i(2); i <= n; ++i)
    {
        if (!isprime[i])
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (register int j(1); j <= cnt and i * prime[j] <= n; ++j)
        {
            isprime[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;
            }
        }
    }
}

欧拉定理

那么为什么要讲欧拉函数呢?就是为了引出欧拉定理!

(a, m) 互质,则 (a^{φ(m)}≡1 (mod m))

([1, m]) 中与 (m) 互质的数列出来,设为 (b_1, b_2, ⋯, b_{φ(m)})

(c_i=acdot b_i  ext{mod }m),可以证明 (c_i) 两两模 (m) 不同余,且任意 (c_i)(m) 互质。

那么 (c) 其实是 (b) 重排的结果,因为与 (m) 互质的数只有 (φ(m)) 个。

因此 (∏ b_i≡∏ c_i≡a^{φ(m)}cdot ∏ b_i (mod m)),得证。

前面提到的费马小定理其实是欧拉定理的子定理。

扩展欧拉定理

刚才的欧拉定理只适用于 (a, m) 互质的情况

对于不互质的情况,此处不证明地给出扩展欧拉定理:

(c<φ(m),则 a^c≡a^c (mod m))

(c≥φ(m),则 a^c≡a^{[c mod φ(m)]+φ(m)} (mod m))

证明比较复杂,有兴趣的同学可以自行查阅或浏览这篇博客

Part 3 上弦月(Hard Mode)

中国剩余定理

BSGS 算法

整除分块(数论分块)

积性函数

莫比乌斯反演

发表回复

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