最小数（欧拉定理）
最小数（欧拉定理）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142633615
http://noip.ybtoj.com.cn/contest/802/problem/7
对 进行一些简单处理，现在相当于变成了一个 和 的关系。
考虑这个东西不好表示，我们可以用 来表示，现在变成了：
，也就是
记 ，一个合法的构造是 ，但我们要求最小 ，所以我们枚举 的所有因子即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2024-08-26
8.26 T2 日记和欧拉函数（欧拉函数）
8.26 T2 日记和欧拉函数（欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575260 http://cplusoj.com/d/senior/p/NOD2301B 发现 x≤Bx\le Bx≤B 时答案是 xxx x>B+500x>B+500x>B+500 左右答案是1 我们预处理中间的就行 预处理直接暴力做，求 maxϕ\max \phimaxϕ 的话相当于求小于它的质数 12345678910111213141...
2024-09-24
欧拉函数 简单题
欧拉函数 简单题 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142256434 φ(n)\varphi(n)φ(n) 表示 nnn 以内和 nnn 互质的数的个数 若 nnn 为质数 φ(n)=n−1\varphi(n)=n-1φ(n)=n−1 φ(pk)=pk−pk−1=pk(p−1)\varphi(p^k)=p^k-p^{k-1}=p^k(p-1)φ(pk)=pk−pk−1=pk(p−1) φ(n)\varphi(n)φ(n) 为积性函数...
2026-07-05
初等数论入门 Lesson 7 阶与原根
初等数论入门 Lesson 7 阶与原根 阶 Order 定义： 对于 gcd(a,m)=1\gcd(a,m)=1gcd(a,m)=1 ordm(a)=min{n∈Z∣an≡1(modm)}\operatorname{ord}_m(a)=\min\{n\in \mathbb Z\mid a^n\equiv 1\pmod m\} ordm(a)=min{n∈Z∣an≡1(modm)} 即不断计算 a1,a2,…a^1,a^2,\dotsa1,a2,…，第一次出现余数为1，那个指数就是阶。 存在性证明： 由欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)}\equiv...
2026-07-04
初等数论入门 Lesson 3 积性函数与狄利克雷卷积
初等数论入门 Lesson 3 积性函数与狄利克雷卷积 积性函数 Multiplicative Function 积性函数定义： f(1)=1,∀a,b gcd(a,b)=1⇒f(ab)=f(a)f(b)f(1)=1, \\ \forall a,b\;\gcd(a,b)=1 \Rightarrow f(ab)=f(a)f(b) f(1)=1,∀a,bgcd(a,b)=1⇒f(ab)=f(a)f(b) 完全积性函数（Completely Multiplicative Function）： f(1)=1f(ab)=f(a)f(b)f(1)=1\\ f(ab)=f(a)f(b)...
2026-07-04
初等数论入门 Lesson 5 欧拉函数
初等数论入门 Lesson 5 欧拉函数 欧拉函数乘积公式 由第三课我们已知 φ(n)=n∏p∣n(1−1p)\boxed{\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)} φ(n)=np∣n∏(1−p1) 欧拉函数的积性我们也证明过： 构造剩余性 A={a∣1≤a≤m, gcd(a,m)=1}A = \{a \mid 1 \le a \le m,\ \gcd(a,m) = 1\}A={a∣1≤a≤m, gcd(a,m)=1}，共 φ(m)\varphi(m)φ(m) 个； B={b∣1≤b≤n, ...
2024-09-23
P4140 奇数国（欧拉函数）
P4140 奇数国（欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142456348 https://www.luogu.com.cn/problem/P4140 等价于我们要求一个区间的积的欧拉函数，单点修改，每个数的最大质因子不超过281. 求积是容易的，然后现在只要求每个因子是否出现。 因为不超过60个因子，所以我们直接暴力即可。 直接树状数组即可。 123456789101112131415161718192021222324252627...