从零开始的数论套路(未完)
:
[SDOI2008]沙拉公主的困惑 题面传送门 上PoPoQQQ大爷的题解 若一个数与互质,那么也一定与互质,也一定与m!互质. 由于一定是的倍数,于是我们每存在到一个与互质,我们就一定能找到个与互质的数 而以内与互质的数的数量恰好是 所以答案等于: 考虑的展开式: &n
BZOJ2705Longge的问题 题面传送门 求 一道有意思的Phi题。 考虑枚举N的约数k,令表示有多少。 那么此时答案变为 因为,那么,即 由Phi的通式可以在根号范围内求解。复杂度这么爆炸的做法我也不知道怎么过的 (为分解质因数里的第个因子) #include <cmath> #include