Tag Archives: Phi

[数论+Phi]BZOJ2186沙拉公主的困惑

Cptraser/ 十月 30, 2018/ 2018.10/ 0 comments

[SDOI2008]沙拉公主的困惑 题面传送门 上PoPoQQQ大爷的题解 若一个数与互质,那么也一定与互质,也一定与m!互质. 由于一定是的倍数,于是我们每存在到一个与互质,我们就一定能找到个与互质的数 而以内与互质的数的数量恰好是 所以答案等于:     考虑的展开式:   &n

Read More

[Phi]BZOJ2705Longge的问题

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

BZOJ2705Longge的问题 题面传送门 求 一道有意思的Phi题。 考虑枚举N的约数k,令表示有多少。 那么此时答案变为 因为,那么,即 由Phi的通式可以在根号范围内求解。复杂度这么爆炸的做法我也不知道怎么过的 (为分解质因数里的第个因子) #include <cmath> #include

Read More