「笔记」数论做题记录

目录

建议配合数论相关复习食用。

会不断更新的。

BSGS

按着下面这个博客刷的,我就不写了。(太懒了

BSGS例题及题解

欧拉定理

P2155 [SDOI2008] 沙拉公主的困惑

根据欧几里得算法的这么个式子 \(\gcd(x,y) = \gcd(x+ky,y)\)。

那么,如果 \(y \mid x\),\(x\) 以内与 \(y\) 互质的数的个数就是 \(\varphi (y) \frac{x}{y}\)(是一个倍数关系)。

所以这题答案为

\[\frac{n!}{m!} \varphi(m!) \]

\(\varphi (m!)\) 其实是可以递推的。

  • 如果 \(m\) 是质数,\(\varphi (m!) = \varphi((m-1)!) \times (m-1)\)。
  • 如果 \(m\) 不是质数,\(\varphi (m!) = \varphi((m-1)!) \times m\)。

那么对于前面的那个分数,都知道当 \(n \ge mod\) 并且 \(m \ge mod\) 时是不能直接算的,因为 \(n!\) 中的 \(mod\) 和 \(m!\) 中的 \(mod\) 有可能会抵消掉。

于是在递推阶乘的时候可以特判一下,当 \(i=mod\) 时直接令 \(n!=(n-1)!\)。

在计算的时候再判断一下,只有当 \(\left\lfloor \frac{n}{mod} \right\rfloor = \left\lfloor \frac{m}{mod} \right\rfloor\) 不满足时答案为 \(0\)。

P4139 上帝与集合的正确用法

显然质数大于模数,根据欧拉定理我们知道

\[a^p \equiv a^{p \% \varphi(m)+\varphi(m)} \pmod m \]

递归处理即可,就做完了,复杂度 \(O(\text{能过})\),(好像是 \(\log\) 级别?)

CF906D Power Tower

求欧拉函数写错了调半天/wul

做法和上个题一样。

但是欧拉降幂的写法我们还是需要注意,一定要严格遵循下列公式:

\[a^p = \begin{cases} a^c, & c < \varphi(m) \\ a^{c \% \varphi(m) + \varphi(m)}, & otherwise \end{cases} \bmod b \]

原因是当 \(\gcd(a,b) \neq 1\) 时,\(a^{\varphi(m)} \equiv 1 \pmod m\) 不一定成立。

具体实现可以在快速幂中处理:

int Pow(int x, int p, int mod) {
    int res = 1;
    while(p) {
        if(p & 1) {
            res = res * x;
            if(res >= mod) res = res % mod + mod; // 欧拉公式
        }
        x = x * x;
        if(x >= mod) x = x % mod + mod; // 欧拉公式
        p >>= 1;
    }
    return res;
}

P3934 [Ynoi2016] 炸脖龙 I

挺水的一道 Ynoi。

上面那题应该算这题的弱化版。

与上面那题的区别是模数不固定和带修。

模数最大为 \(2 \times 10^7\) 直接线筛即可,带修可以分块或者树状数组,实测他们的实际速度差不多。

这里鸣谢 @NaCly_Fish 的写法,可以判断指数与模数的大小关系,以便遵守欧拉公式。()

struct node { int sum; bool flag; };
node Pow(int x, int p, int mod) {
    node res = (node){1, false};
    if(x >= mod) x %= mod, res.flag = true;
    while(p) {
        if(p & 1) {
            res.sum *= x;
            if(res.sum >= mod) {
                res.flag = true;
                res.sum %= mod;
            }
        }
        x = x * x;
        if(x >= mod) {
            res.flag = true;
            x %= mod;
        }
        p >>= 1;
    }
    return res;
}

node Solve(int l, int r, int p) {
    int x = a[l] + tag[pre[l]]; // 分块
//    int x = Query(l); // 树状数组
    if(p == 1) return (node){0, true};
    if(x == 1) return (node){1, false};
    if(l == r) return x < p ? (node){x, false} : (node){x % p, true};
    node res = Solve(l + 1, r, phi[p]);
    if(res.flag) res.sum += phi[p];
    return Pow(x, res.sum, p);
}

P3747 [六省联考 2017] 相逢是问候

发现一个点修改多次只后就相当于 \(c^{c^{c^{...}}} \bmod p\),那个 \(a_i\) 就被忽略掉了。大约是 \(\log p\) 次。

所以考虑暴力修改,然后维护修改次数最小值。

但是这样复杂度是 \(O(n \log^3 n)\)。 (线段树 + 欧拉降幂 + 快速幂)

会被卡的很惨。

所以这题的正确姿势是,预处理快速幂。

假设求 \(x^c\),因为 \(p\) 只有 \(10^8\),所以 \(c = c / 10000 + c \% 10000\),所以可以分别预处理这两部分,计算的时候直接合并可以做到 \(O(1)\)。

此时总复杂度 \(O(n \log^2 n)\)。

扩展中国剩余定理

P4774 [NOI2018] 屠龙勇士

真是一道既浪费了时间又玩崩了心态的好题呢。

题意就是解形如 \(b_ix \equiv a_i \pmod {p_i}\) 的同余方程组。

1、假设已经得到了前面 \(i-1\) 个方程的解 \(ans\);
2、设 \(M = \text{lcm}(p_1,p_2,...,p_{i-1})\),则对于任意整数 \(x\),\(ans +xkM\) 是前 \(i-1\) 个方程的通解;
3、想得到前 \(i\) 个方程的解,就要满足 \(b_i(ans+xM) \equiv a_i \pmod {p_i}\),移项得。
4、\(b_iM x \equiv a_i - b_i ans \pmod {p_i}\)。
5、显然可以用扩欧,直接转化成 \(Ax+By = C\) 求解即可。

\[(b_iM)x + (p_i)y = (a_i - b_i ans) \]

然后注意的一点是有很多地方会爆 long long,注意加上龟速乘。

上一篇:数学


下一篇:[设计模式] 20 状态模式 State Pattern