求
其中0<N<=2^32
看起来是莫比乌斯反演,其实不是。。。。。。
化一波式子先
然后别化了(手动喷血
后面那个求和号不就是欧拉函数的定义么(手动喷血
然后变成了求
什么?枚举因子个数和求欧拉函数都是
注意到这里要求的都是N的因子的欧拉函数的值,因此可以对N质因数分解,然后直接用dfs枚举各质因子的次数来枚举因子,并且在dfs过程中能直接用欧拉函数的公式维护出欧拉函数值,然后复杂度就变成了O(因子的个数),也就是
代码(48ms)
|
求
其中0<N<=2^32
看起来是莫比乌斯反演,其实不是。。。。。。
化一波式子先
然后别化了(手动喷血
后面那个求和号不就是欧拉函数的定义么(手动喷血
然后变成了求
什么?枚举因子个数和求欧拉函数都是
注意到这里要求的都是N的因子的欧拉函数的值,因此可以对N质因数分解,然后直接用dfs枚举各质因子的次数来枚举因子,并且在dfs过程中能直接用欧拉函数的公式维护出欧拉函数值,然后复杂度就变成了O(因子的个数),也就是
代码(48ms)
#include <iostream> |
Except as otherwise noted, this blog is licensed under CC BY-SA 4.0 License.
©2021-
searchstar
|
pv
|
uv
Theme Tree
by Wu Jun
Powered by Hexo