这里记录着我对题目的奇思妙想。因为我找不到oj，但是我又觉得这种题目很典，所以就搞了一个专门记录的帖子。不保证代码和分析全队，正确性由gemini3 pro支持…

1

  • 题目描述
    • 给出长度为n的数组ai（均为正整数），给出m，选择子序列使得子序列里面的乘积==n
  • 解法解答：使用拆因子dp做法->在已经有的因子里面选择（这里一个实现难点是不能重复，而愚蠢的zues一开始没实现这个），跑背包dp
  • 跑过随机数据代码：
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
46
47
48
49
50
51
52
53
54
55
void solve()
{
    int n;
    cin >> n;
    int m;
    cin >> m;
    // m = 67;

    map<int, int> mp;

    for (int i = 0; i < n; i++)
    {
        int d;
        cin >> d;
        if (m % d == 0)
        {
            mp[d]++;
        }
    }

    map<int, int> dp;
    dp[1] = 1;

    for (auto [nb, cnt] : mp)
    {
        vi now;
        for (auto it : dp)
        {
            now.push_back(it.first);
        }

        for (int j = 0; j < now.size(); j++)
        {
            ll sum = now[j];
            for (int i = 0; i < cnt; i++)
            {
                sum *= nb;
                if (m % sum == 0)
                {
                    if (sum == m)
                    {
                        cout << "yes" << '\n';
                        return;
                    }
                    else
                    {
                        dp[sum]++;
                    }
                }
            }
        }
    }
    cout << "no" << '\n';
}