【梅森素数】POJ 1777 Vivian’s Problem

首先介绍梅森素数的概念:若素数$P=2^m-1$那么$P$被称为梅森素数。

结论一:对于$2^m-1$是素数,$2^{m-1}\times (2^m-1)$为完全数(完全数即为所有因子和等于自身的数)

结论二:“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”。$N$的约数和幂次是可以直接由构成它的梅森素数的来源幂次相加而得的:$(2^2-1)\times (2^3-1)=21$,$21$的约数和为$32=2^5$;

 

Int以内的梅森素数:3、7、31、127、8191、131071、524287、2147483647($m=2、3、5、7、13、17、19、31$)

 

现在轮到这道题,题意如下:

给出K个数,p1,p2,……pk,不一定是素数,给这些数添加指数,0-10之间,最终的乘积为n,他的所有因子和为m,问是否存在一个m为2的幂,如果有多个输出最大的指数,如果没有输出NO。

因为我们知道了梅森素数的结论,于是我们就知道包含且仅包含梅森素数的因子才会被使用,有因为数据范围内梅森素数的个数只有8,我们不妨状压一下。

代码如下:

 

关于“【梅森素数】POJ 1777 Vivian’s Problem”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注