【数论】poj1777 Vivian's Problem（梅森素数）

题意：给定k个数，然后为每个数添加一个幂ei（0=<ei<=10），最后k项累乘的结果为M，如果M的所有因子的和可以写成2^x,求x的最大值，如果没有条件满足，输出NO。

刚看到题没什么思路，解题需要一些结论。

1：梅森素数

所谓梅森数，是指形如2p－1的一类数，其中指数p是素数，常记为Mp 。如果梅森数是素数，就称为梅森素数。

（下文中将梅森素数的指数P称为梅森指数）

（推荐看一下百度百科，多了解一些）

2：

关于梅森素数，有一个重要的定理：“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”，注意不能重复，

比如说3是梅森素数，9就不满足约数和为2的幂，

并且这个幂次正好等于作为因子的梅森素数的梅森指数的和。

比如 3(2的2次幂-1)X7(2的3次幂-1) =21;

21的因数和1+3+7+21=32=2^5;

解题思路：

知道上面两个结论，这题就很明确了。只要找到题中所给的梅森素数，或梅森素数的累乘，则一定满足题干要求。

不是梅森数则幂次为0，梅森数不能重复作为因子出现，幂次为1。如果没有则输出NO。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
#define MAXN 105
int mp[8] = {2,3,5,7,13,17,19,31} ;
int mason[10];
int ans, cnt, status[MAXN];
int k, a;
void get(int a) {
//判断是否梅森素数，同时将状态存入status数组
status[cnt] = 0;
for (int i = 0; i < 8 && a >= mason[i]; i++)
if (a % mason[i] == 0) {
status[cnt] |= 1<<i;
//状压，位数代表对应的梅森指数
a /= mason[i];
if (a % mason[i] == 0)
return;
}
if (a == 1)
cnt++;
}
int
calc(int st) {
int res = 0;
for (int i = 0; i < 8; i++)
if (st & (1<<i))
//因数和S 与 梅森素数对应的指数之和x 关系： S=2^x；求出X即可。
res += mp[i];
return res;
}
void dfs(int cur, int st) {
ans = max(ans, calc(st));
for (int i = cur; i < cnt; i++)
if ((st & status[i]) == 0)
//如果作为因数的梅森素数没有重复，则相乘
dfs(i+1, st | status[i]);
}
int main() {
for (int i = 0; i < 8; i++)
mason[i] = (1 << mp[i]) - 1;
while (scanf("%d", &k) != EOF) {
cnt = 0;
for (int i = 0; i < k; i++) {
scanf("%d", &a);
get(a);
}
if (cnt == 0) {
printf("NOn");
} else {
ans = 0;
dfs(0, 0);
printf("%dn", ans);
}
}
return 0;
}

最后

以上就是威武金针菇为你收集整理的【数论】poj1777 Vivian's Problem（梅森素数）的全部内容，希望文章能够帮你解决【数论】poj1777 Vivian's Problem（梅森素数）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。