【做题笔记】数论做题笔记-526互联

前言

初等数论学习I

Euclid Problem：板题，用 \(exgcd\) 求出的两个解就是 \(|x|+|y|\) 最小的整数解

Gift Dilemma：将方程变为 \(ax+by\equiv p-cz\)，枚举 \(c\) 前的系数，若 \(n=\frac{p}{c}\)，那么时间复杂度为 \(O(Tn\log n)\)

[POI2005] SKO-Knights：如果能到达原先所有横坐标，并且能到达原先所有纵坐标，就可以到达原先所有坐标。为了方便考虑令最后分出的两个向量中有一个竖直向量，由于它只会对竖直方向有影响，所以另一个非竖直向量横坐标应该为 \(\gcd(a_1,a_2...a_n)\)。也就是若现在在合并 \(a[i],a[i+1]\)，首先求出 \(a[i]x+a[i+1]y=\gcd(a[i],a[i+1])\) 的解，那么非竖直向量应该是 \((a[i]x+a[i+1]y,b[i]x+b[i+1]y)\)，记为 \((A,B)\)。人话说就是 \(x\) 个 \(i\) 向量和 \(y\) 个 \(i+1\) 向量合并。通过向量 \((A,B)\)，我们只能走到 \((a,a/A\times B)\)，但是我们要走到 \((a,b)\)，所以竖直向量纵坐标要调整到 \(b-a/A\times B\)。同理可得竖直向量为 \((0,\gcd(b-a/A\times B,a-b/B\times A))\)

[POI2011] SEJ-Strongbox：由于 \(a\) 可以与 \(b\) 相等，因此若 \(k\) 为密码，那么 \(2k,3k,4k...\lfloor\frac{n}{k}\rfloor k\) 都是密码。由此可得，由于前 \(k-1\) 个数都不是密码，所以它们的因子也都不是密码。而最小的密码一定在第 \(k\) 个数因子的集合里。将之前所说的因子划掉，留下的最小的因子就是最小的密码 \(x\)，又因 \(x\) 的倍数都是密码，答案即为 \(\frac{n}{x}\)。稍微优化一下就是直接划掉 \(\gcd(a[i],a[k])\) 的因子，然后再在 \(\gcd(a[k],n)\) 中找。

[WC2021] 斐波那契：没写，期待发货

[POI2012] WYR-Leveling Ground：没写，期待发货

ETF - Euler Totient Function：欧拉函数板子

Irreducable Basic Fractions：欧拉函数板子

Enumerating Rational Numbers：先预处理欧拉函数，再二分出分母，最后暴力出分子。

上帝与集合的正确用法：一个奇怪的结论，当 \(x^{x^{x^{x^x...}}}\) 的指数够大的时候，这就是一个确定的值。令 \(f(x)\) 表示指数为 \(x\) 时的结果，每次递归 \(f(x\bmod\varphi (x)+\varphi(x))\)，在 \(x=1\) 的时候返回 \(0\) 即可。

[[六省联考 2017] 相逢是问候：没写，期待发货

[TJOI2007] 可爱的质数/【模板】BSGS：板子

[SDOI2011] 计算器：拼凑题，需要注意的是 BSGS 时 \(a\) 可能是 \(p\) 的倍数，需要特判一下。

MOD - Power Modulo Inverted：扩展 BSGS 板子

SDOI2013] 随机数生成器：较恶心的推式子题，一顿乱推首先不难得出 \(x_i\equiv a^{i-1}x_1+b\sum\limits_{j=0}^{j-2}a^j\pmod p\)，后面这西格玛是等比数列，运用等比数列求和公式易将其化为 \(x_i\equiv a^{i-1}x_1+b\frac{1-a^{i-1}}{1-a}\pmod p\)，接着一顿化到 \(x_1\times a^{AT}+k\times a^{AT}\equiv t\times a^B+k\times a^B\)，就可以用大步小步做了。

【模板】中国剩余定理（CRT）/ 曹冲养猪：板题

【模板】扩展中国剩余定理（EXCRT）：板题

[NOI2018] 屠龙勇士：恶心题\ouu，但也教会了我许多细节处理。首先显然每次选择的剑都是唯一的，这个可以考虑用 multiset 或手写平衡树预处理出来，记为\(atk[i]\)，然后建立方程组 \(atk_i\times x\equiv a_i\pmod {p_i}\)，接着用扩展中国剩余定理随便搞一下。

[COCI2012-2013#6] BAKTERIJE：没写，期待发货

[SDOI2010] 古代猪文：实际上求 \(p=\sum\limits_{d|n} \dbinom{n}{d}\)。先用个欧拉 \(g^{ansi}\equiv g^{ansi\;\bmod\;\varphi(mod)}\pmod {mod}\)，而由于模数是质数，所以 \(\varphi(mod)=mod-1\)。但此时用 Lucas 由于模数太大了还会挂，考虑将 \(mod-1\) 质因数分解为 \(2\times3\times4679\times35617\)，问题就转化为求线性方程组\(\begin{cases}x\equiv ansi\pmod 2\\x\equiv ansi\pmod3\\x\equiv ansi\pmod {4679}\\x\equiv ansi\pmod {35617}\end{cases}\)，再用一下 Lucas 定理即可。

小 A 与两位神仙：没写，期待发货

[ WC2020] 猜数游戏：没写，期待发货

「SWTR-8」幂塔方程：没写，期待发货

【模板】二次剩余：板子

[Code+#7] 同余方程：没写，期待发货

【模板】卢卡斯定理/Lucas 定理：板子

【模板】扩展卢卡斯定理/exLucas：没学，期待发货

初等数论学习II

【模板】Pollard-Rho：板子

初等数论学习III

完全平方数：设 \(f(n)\) 表示 \(n\) 的范围内所有不讨厌的数，最后只需要二分答案一下即可。接下来的想法大概是线性筛出值域范围内所有小 X 不讨厌的数，但是值域范围内显然无法实现这一点。如果直接筛去 \(2^2,3^3,4^4...\) 的倍数的话，\(2^2\) 和 \(4^4\) 的倍数显然会有一部分重复，人话说就是会有一些数被减去多遍，这显然是不好的。而由于 \(4^4\) 的倍数会完全包含在 \(2^2\) 的倍数的集合里面，所以我们先只考虑筛质数的平方的倍数。

但是此时在筛 \(2^2\) 的倍数和 \(3^3\) 的倍数时，\(36\) 会在 \(2\times 2\times 9\) 和 \(3\times 3\times 4\) 的时候都被减去一次，所以类似地，我们考虑再加上 \(6^2,10^2,14^2...\) 的倍数。然后又会有数被加多遍，所以又要再减去.....以此类推，就可以得到容斥的想法。

综上，我们枚举 \(i\) 表示 \(i\) 的平方的倍数对答案有多少贡献，显然有在 \(n\) 里面 \(i\) 的平方的倍数有 \(\lfloor\frac{n}{i^2}\rfloor\)。再结合前面的讨论，归纳一下可得当 \(i\) 有奇数个不同质因子的时候贡献为 \(1\)，有偶数个的时候贡献为 \(-1\)。因此得到 \(f(n)=\sum\limits_{i=1}^{\sqrt n} \mu(i)\lfloor\frac{n}{i^2}\rfloor\)。

一个比较细节的地方是打表发现最后的答案不会超过 \(n\) 的两倍，所以二分的边界和预处理 \(\mu(x)\) 的边界由此可以确定。