解题思路

本题的核心在于判断由给定数构成的 ( N ) 的约数之和 ( M ) 是否为 2 的幂，并求最大指数 ( x )。关键在于利用数论中约数和的性质以及梅森素数的特性。

关键分析

1. 约数和公式：
   若 ( N = \prod p_i^{e_i} )，则其约数和为 ( M = \prod (1 + p_i + p_i^2 + \dots + p_i^{e_i}) )。
   ( M ) 为 2 的幂的充要条件是每个因子 ( (1 + p_i + \dots + p_i^{e_i}) ) 均为 2 的幂，且它们的乘积也是 2 的幂。

2. 梅森素数的性质：
   形如 ( p = 2^q - 1 ) 的素数（如 3, 7, 31 等）称为梅森素数。当 ( p ) 是梅森素数且 ( e_i = 1 ) 时，( 1 + p = 2^q )，即该因子为 2 的幂。
   若 ( p_i = (2^q - 1)^e )（( e \leq 10 )），则 ( 1 + p_i + p_i^2 + \dots + p_i^e = \frac{p_i^{e+1} - 1}{p_i - 1} = \frac{(2^q - 1)^{e+1} - 1}{2^q - 2} )，仅当 ( e = 1 ) 时为 2 的幂（此时因子为 ( 2^q )）。

3. 状态压缩与DFS：
   预处理前 8 个梅森素数及其指数 ( q )。对于每个输入数 ( p_i )，检查其是否为某个梅森素数的幂（( e \leq 10 )），并将合法状态压缩为二进制位（每位对应一个梅森素数）。通过DFS遍历所有不冲突的状态组合，计算最大指数和。

解决代码

#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("NO\n");
        } else {
            ans = 0;
            dfs(0, 0);
            printf("%d\n", ans);
        }
    }
    return 0;
}

代码解释

1. 预处理梅森素数：
   定义梅森素数及其对应的指数 ( q )，用于快速判断输入数是否为其幂。

2. 状态检查函数check：
   对每个输入数 ( a )，检查其是否为某个梅森素数的幂（指数 ( e \leq 10 )）。若有效，将对应的梅森素数指数位标记为1（状态压缩）。

3. 枚举有效组合：
   遍历每个数的状态，尝试与其他数的状态合并（确保梅森素数不重复），计算最大指数和。若无法形成有效组合，输出"NO"，否则输出最大指数。

该算法通过数论分析和状态压缩，高效地筛选出符合条件的约数和，确保了在较大数据范围内的正确性和性能。