首页 > 题解 > bzoj 3643 Phi的反函数

bzoj 3643 Phi的反函数

Description

Input

Output

Sample Input

4

Sample Output

5

题解

学长出的题%%%

转个学长的题解

这题用到了一个非常常用非常重要的性质:对于long long级别的数字,它不同的质因子个数非常小,最多不会超过15个。因为最小的十来个质数乘起来就已经变得很大了。这就说明我们可以用爆搜来搞这个东西。对于这道题来说我们知道一个数的phi就是一坨质数和一坨(质数-1)的乘积,那么我们的任务就是把这些东西构造出来。

枚举所有的prime,如果这个prime合法的话那么prime-1一定是给定的x的约数。如果x不能整除prime-1的话就根本不用考虑这个质数了,否则就开始考虑把prime这个东西构造到答案里面去。首先除掉一个prime-1,答案乘以一个prime;接下来就一个一个地除掉prime,然后每次都进去搜一次直到不能除了为止,这相当于枚举了这个质因数的次数。

然而还有一个问题就是对于那些很大的质数没法筛出来,这就要利用每个数大于$\sqrt x$的质因子只会有一个,并且这个质因子一定表现为prime-1的形式,那么每次就判断一下当前剩下的这个数+1是不是一个大质数,如果是大质数的话就记录答案并且不用继续往下搜了,因为再往下搜答案只会再变大。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×