uva 1323 - Vivian's Problem(梅森素数)

本文主要是介绍uva 1323 - Vivian's Problem(梅森素数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 1323 - Vivian's Problem

题目大意：给定N个数，然后为每个数添加一个幂ei，最后N项垒乘的结果为M，要是得M的所有因子的和可以写成2x,求x的最大值，如果没有条件满足，输出NO

解题思路：若一个数可以写成若干个不同的梅森素数的乘积，那么这个数的所以因子和可以写成2x.
232−1的范围内只有8个梅森素数，所以可以用状压处理。

梅森素数即为2^i-1形式的素数

/*********************** 梅森素数，(2^k) - 1** 一个数若能差分成若干个不同的梅森素数的积，那么该数的所有因子和可以写成2^n形式。*
**********************/
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int maxp = 8;
const int f[maxp+5] = {2, 3, 5, 7, 13, 17, 19, 31};
int N, ans, s[105];
ll  mpri[maxp+5];void insert (ll u) {s[N] = 0;for (int i = 0; i < maxp; i++) {if (u % mpri[i] == 0) {s[N] |= (1<<i);u /= mpri[i];if (u % mpri[i] == 0)return;}}if (u == 1)N++;
}int solve (int S) {int ret = 0;for (int i = 0; i < maxp; i++)if (S&(1<<i))ret += f[i];return ret;
}void dfs (int d, int S) {ans = max(ans, solve(S));for (int i = d; i < N; i++)if ((S&s[i]) == 0)dfs(i+1, S|s[i]);
}int main () {for (int i = 0; i < maxp; i++)mpri[i] = (1LL<<f[i]) - 1;ll n, a;while (scanf("%lld", &n) == 1) {N = 0;for (int i = 0; i < n; i++) {scanf("%lld", &a);insert(a);}if (N == 0)printf("NO\n");else {ans = 0;dfs(0, 0);printf("%d\n", ans);}}return 0;
}