T30947: Ask for Likes

math, dfs, http://cs101.openjudge.cn/pctbook/T03094/

小 L 也跟风发了一条 QQ 消息，随后群 u 们便开始在下面扣表情。

已知 QQ 支持 n 种表情，编号 1 ~ n。

现在小 L 发的消息获得了 c[i] 个第 i 种表情。

他想要让所有存在的表情数量之积为 x，即所有非零的 c[i] 之积为 x。特别地，当不存在非零 c[i] 时，认为积为 1。

他想到了找人来继续扣表情，即进行若干（可以为零）次操作，每次选定一个 i 并令 c[i] 加 1。

他想考考你，通过这样的操作，是否可能达成他的目标。

每次询问独立，即他并不会真的找人来继续扣表情。

即：给出一个长度为 $n$ 的非负整数数组 $c$ （代表初始表情数），每次操作可以令任意 $c [i] \leftarrow c [i] + 1$ （即可变大，不可变小）。现有 $q$ 次独立询问，每次给出一个目标值 $x$ ，问能否通过若干次操作，使数组中所有非零元素的乘积刚好等于 $x$ 。

输入

第一行，两个整数 n, q（1 <= n <= 10^5, 1 <= q <= 100）。

第二行，n 个整数 c[1], ..., c[n]（0 <= c[i] <= 10^9）。

接下来 q 行，每行一个整数 x（1 <= x <= 10^9），表示一次询问。

输出

q 行，每行一个字符串 Yes 或 No，分别表示能或不能达成小 L 的目标。

样例输入

20 5
2 5 5 2 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
600
800
1000
1200
1400

样例输出

No
Yes
Yes
Yes
Yes

提示

样例的初始状态就是图中的情形，唯一的区别是这里假定 QQ 中只能使用这 20 种表情。

对于第一次询问，由于现在表情数量之积大于 600，继续扣表情只会将该值继续增大，故输出 No。

对于第二次询问，由于现在表情数量之积恰好为 800，他不需任何操作就能达成目标，故输出 Yes。

对于第三次询问，他只需将第 5 种表情（图中的“毛毛虫”）再扣 2 次即可达成目标，故输出 Yes。

对于第四次询问，他只需将第 1 种表情（图中的“牛气冲天”）或第 4 种表情（图中的“拜谢”）再扣 1 次即可达成目标，故输出 Yes。

对于第五次询问，他只需将第 2 种表情（图中的“咦”）或第 3 种表情（图中的“棒棒糖”）再扣 2 次，并将第 5 种表情再扣 2 次，即可达成目标，故输出 Yes。

------

约数分解，深度优先搜索 (DFS)

来源：2026 spring, Leasier

“加 1 操作” $⟹$ 转化为了数学上的 “选择一个 $\geq$ 原数的约数”。

“DFS 代码” $⟹$ 则是用来不断试错、回溯，直到帮所有数字找到一组“乘积刚好等于 $x$ ”的完美搭配。

python

import sys
from functools import lru_cache
from bisect import bisect_left

sys.setrecursionlimit(2000)


def solve():
    # 极简读取输入
    raw = sys.stdin.read().split()
    if not raw: return
    n, q = int(raw[0]), int(raw[1])
    c = [int(x) for x in raw[2:n + 2]]
    queries = [int(x) for x in raw[n + 2:]]

    # 1. 分类：sz_zero 是万能位个数，Y 是固定位列表
    sz_zero = sum(1 for x in c if x <= 1)
    Y = sorted([x for x in c if x >= 2], reverse=True)

    for x in queries:
        # if len(Y) > 30:  # 边界截断
        #     print("No")
        #     continue

        # 2. O(sqrt(x)) 极简约数生成
        divs = []
        for i in range(1, int(x ** 0.5) + 1):
            if x % i == 0: divs.extend([i, x // i])
        divs = sorted(set(divs))

        # 3. 极简 DFS 搜索
        @lru_cache(None)
        def dfs(idx, R):
            # if R < (1 << (len(Y) - idx)): return False  # 剩余空间不够剪枝
            if idx == len(Y): return sz_zero > 0 or R == 1

            # 查找所有 >= Y[idx] 且能整除 R 的约数
            for d in divs[bisect_left(divs, Y[idx]):]:
                if d > R: break
                if R % d == 0 and dfs(idx + 1, R // d): return True
            return False

        print("Yes" if dfs(0, x) else "No")


if __name__ == '__main__':
    solve()

T30947: Ask for Likes ​

T30947: Ask for Likes