最小数（欧拉定理）
最小数（欧拉定理）
本文搬运自本人高中时期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-09-25
集合统计（拆mod关系式 + 欧拉函数）
集合统计（拆mod关系式 + 欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142521016 http://noip.ybtoj.com.cn/contest/802/problem/6 对于： n mod k+m mod k≥kn\bmod k+m\bmod k\ge knmodk+mmodk≥k ，我们可以先把 mod \bmodmod 拆掉： n−⌊nk⌋×k+m−⌊mk⌋×k≥kn-\lfloor \dfrac n k\rfloo...
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)...
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 6 同余方程与中国剩余定理
初等数论入门 Lesson 6 同余方程与中国剩余定理 剩余系 完全剩余系：一组数 a1,a2,…,ama_1,a_2,\dots,a_ma1,a2,…,am 称为模 mmm 的一个完全剩余系，如果它们分别取自模 mmm 的 mmm 个不同的剩余类。 有以下两种典型的剩余系： 最小非负剩余系：{0,1,2,…,m−1}\{0, 1, 2, \dots, m - 1\}{0,1,2,…,m−1} 绝对最小剩余系：{−⌊m2⌋,…,−1,0,1,…,⌈m2⌉}\left\{ -\left\lfloor \frac{m}{2} \right\rfloor, \dots, -1, 0...
2024-09-23
P4140 奇数国（欧拉函数）
P4140 奇数国（欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142456348 https://www.luogu.com.cn/problem/P4140 等价于我们要求一个区间的积的欧拉函数，单点修改，每个数的最大质因子不超过281. 求积是容易的，然后现在只要求每个因子是否出现。 因为不超过60个因子，所以我们直接暴力即可。 直接树状数组即可。 123456789101112131415161718192021222324252627...
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...