题解 - [POJ 1777] [UVA 1323] Vivian's Problem

发表于 更新于 分类于 ， 本文字数： 709 阅读时长 ≈ 3 分钟

题目链接

原始题面

Description

The desire to explore the unknown has been a driving force in human history since the dawn of time. From the earliest documented accounts, ancient civilizations had explored the earth by sailing around. Early adventurers were motivated by religious beliefs, the desire conquest, the need to establish trade routes, and hunger for gold

You never know what will happen before the exploration. Neither does Bruce Lee. Someday, Mr.Lee entered a desolate tropical rainforest. And after several days' exploring, he came in front of a cave with something blinking in it. A beautiful girl named Vivian came out just before he tried to go into the cave. And Vivian told Mr. Lee that he must answer some questions before he entered the cave. As the best friend of Mr. Lee, you should help him to work it out

You will get \(k\) positive integers \(p_1, p_2 ... p_i ... p_k\) (\(1 \leqslant i \leqslant k\)) from Vivian. From these numbers, you can calculate \(N, N=\prod_{i=1}^k p_i^{e_i}\) (\(0 \leqslant ei \leqslant 10, \sum_{i=1}^ke_i\geqslant1, 1 \leqslant i \leqslant k\)); you may decide the integers eias you wish. From one N, you can calculate corresponding \(M\), which equals to the sum of all divisors of \(N\). Now, you should tell Vivian whether or not there is an \(M\) which is the power of \(2\) (\(1,2, 4, 8\), and \(16\) … so on). If there's no \(N\) can make M equal to the power of 2, tell Vivian "NO". If \(M\) equals to some \(2^x\), then show her the exponent (\(x\)). And if there are several \(x\), only show her the largest one

Input

Input contains several testcases. For each testcase, the first line contains only one integer \(k\) (\(0 < k \leqslant 100\)), representing the number of positive integers. Then there are \(k\) positive integers \(p_1, p_2 ... p_i ... p_k\) (\(1 < pi < 2^{31}, 1 \leqslant i \leqslant k\)) in the second line, representing the given numbers

Input is terminated by end of file

Output

For each testcase, you should output your result in a single line. If you can find N from the given numbers, output the largest exponent. Otherwise, output "NO". Extra spaces are not allowed

Sample Input

1
2
3
4
1
2
3
2 3 4

Sample Output

1
2
NO
2

Source

Asia Guangzhou 2003

题意简述

给出一组数 \(p_1,p_2,\dots,p_k\), 设 \(N=\prod_{i=1}^kp_i^{e_i}\), 其中 \(0\leqslant e_i\leqslant 10,i=1,2,...,k,~\sum_{i=1}^ke_i\geqslant 1\), \(M\) 为 \(N\) 的因子和，问是否有一组数 \(e_1,e_2,\dots,e_k\) 使得 \(\log_2M\in\mathbb{N}\), 如果有，输出可能的 \(x\) 中的最大值

解题思路

我们首先有这样一条定理

定理 - 1

\[ M=2^{\sum_{i=1}^sx_i}\iff N=\prod_{i=1}^s(2^{x_i}-1),~2^{x_i}-1~\text{is}~\text{mersenne}~\text{prime}, i=1,2,...,s \]

\(\Box\)

其正确性是显然的

由这条定理，我们只需判断能否选取一组数 \(e_1,e_2,\dots,e_k\in\{0,1\}\) 使得 \(N\) 为几个不同的 Mersenne 素数的乘积，即在 \(p_1,p_2,\dots,p_k\) 中选取一些数使得 \(N\) 为几个不同的 Mersenne 素数的乘积

我们注意到在 \([1,2^{31}]\) 中只有 \(8\) 个 Mersenne 素数，分别为 \(2^{2}-1,2^{3}-1,2^{5}-1,2^{7}-1,2^{13}-1,2^{17}-1,2^{19}-1,2^{31}-1\)

因为 \(N\) 与这些 Mersenne 素数之间的整除关系的状态种数较少，所以这里我们可以考虑使用状压 DP

代码参考

Show code

POJ_1777view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
#include <cstring>
const int S = 1 << 8, mers_exp[] = {2, 3, 5, 7, 13, 17, 19, 31};
#define mers_pri(i) ((1 << mers_exp[i]) - 1)
int judge(int n) {
  int ans = 0;
  for (int i = 0; i < 8; ++i)
    if (n % mers_pri(i) == 0) {
      ans |= (1 << i);
      n /= mers_pri(i);
    }
  return n == 1 ? ans : 0;
}
bool f[S];
int status[S];
int main() {
  int k;
  while (~scanf("%d", &k)) {
    memset(f, 0, sizeof(f));
    int cnt_status = 0;
    for (int i = 1, _; i <= k; ++i) {
      scanf("%d", &_);
      if (_ = judge(_)) f[status[++cnt_status] = _] = 1;
    }
    for (int i = 1; i <= cnt_status; ++i)
      for (int j = 0; j < S; ++j)
        if (f[j] && !(j & status[i])) f[j | status[i]] = 1;
    int ans = 0;
    for (int i = S - 1, _ = 0; i; --i, _ = 0)
      if (f[i]) {
        for (int j = 0; j < 8; ++j)
          if ((1 << j) & i) _ += mers_exp[j];
        ans < _ ? ans = _ : 0;
      }
    if (ans) printf("%d\n", ans);
    else puts("NO");
  }
}