专栏文章

小B的疑问 Easy Version

BBelieve_in_dreams
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0ewr8
此快照首次捕获于
2025/12/01 18:31
3 个月前
此快照最后确认于
2025/12/01 18:31
3 个月前
查看原文

小B的疑问 Easy Version

时间限制：C/C++ 1000MS ，其他语言 2000MS
内存限制：C/C++ 256MB ，其他语言 512MB

描述

Believe_in_DreamsBelieve\_in\_Dreams 同学一直有一个疑问，你来帮帮他吧！
现在给出一个整数 TaskTask 和一个正整数序列 aa，有 nn 个元素。
我们定义一次操作为选择一个正整数 xx，并将所有序列中为 xx 的倍数的数字都减去 xx 再减去 TaskTask 。
小 BB 想要知道最少经过多少次操作才能够将这个序列变成非正整数序列。

输入描述

第一行两个正整数 TaskTask 和 nn 表示有 nn 个数字在序列 aa 中。
第二行有 nn 个整数，表示这个序列。

输出描述

一行一个整数，表示最少经过多少次操作才能够将输入序列变成非正整数序列。

用例输入 1

CPP
1 2  
2 4

用例输出 1

CPP
2

用例输入 2

CPP
1 2  
1 2

用例输出 2

CPP
1

用例输入 3

CPP
1 4  
2 6 8 12

用例输出 3

CPP
3

提示

样例：

样例解释1：
第一次x=2 第二次x=4
样例解释2：
第一次x=1
样例解释3：
第一次x=3 第二次x=2 第三次x=5

范围：

数据为样例，因为该问题目前没有被解决。

问题解决进度&看法：

AI

AIchatos10
提出贪心&优先队列算法，无法通过样例。
豆包 AI
提出贪心算法，无法通过样例。 提出动态规划算法，无法通过样例。
百度 AI
提出广度优先搜索的变体，无法通过样例。
Deepseek
提出贪心算法，无法通过样例。 多次思考超过 10000 字后终止思考。

OIer

Believe_in_Dreams 本人
能够建模成图论问题。 已经解决 Task≤0 的情况。 能够使用暴力解决 Task>0 的情况。
C24 zgr
有思路解决。
C23 hsh
没有思路解决。
MoonCake2011
这 SB 题吧这，干什么吃的， Task 0 够了。
char
认为无法建模成图论，可能是 NP−Hard 问题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...