网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P4780
2024-09-24
P4780 Phi的反函数 题解
因为\(\varphi(x)\)的值只与\(x\)的不同质因子有关,又因为\(2^{31}\)之内的数的质因子个数不超过\(10\),所以容易枚举\(10\)个位置上填入的质因子打出朴素的暴力,简单剪枝后得到\(20\)分。注意需要先判掉\(x=n+1\)的情况。考虑优化:因为\(\varphi\)的值只与质因