#P18535. Generalized Collatz Conjecture
Generalized Collatz Conjecture
Generalized Collatz Conjecture
你是一位满怀热情的本科生,看过一段关于 Collatz 猜想的 YouTube 视频对 Collatz 猜想做了深入研究,并灵光一现,想出了几个绝妙的解决办法!你已经开始想象:本科毕业论文将解决 Collatz 猜想,让你的名字与冯·诺伊曼、陶哲轩和拉马努金这样的天才一同写入教科书。导师认为这不是一个好主意,提醒你已有许多人尝试并失败。但他们不懂:别人是别人,你是你;这次不同,你是特别的。
由于你的坚持,导师勉强同意支持你,但条件是先解决下面这个比 Collatz 猜想的设定更困难、更一般的问题,以证明自己的能力。
给定一个由互不相同的整数组成的集合 和整数 。你可以执行以下两种操作:
- 选择一个 ,将 替换为 。
- 选择当前 的一个素因子 ,将 替换为 。
求将 变为 所需的最少操作次数。如果无法做到,也请报告。
输入格式
第一行包含测试用例数 。接下来有 行,每行描述一个测试用例。
每行包含 个以空格分隔的整数:前两个整数为 和 ,接下来 个整数为集合 的元素。
- 。
- 。
- 。
- 对每个 ,。
- 同一输入文件中,没有两个测试用例完全相同,即不存在重复的 。
- 的元素按严格递增顺序给出。
输出格式
对每个测试用例输出一行,包含以下两者之一:
- 将 变成 所需的最少操作次数,输出一个整数;
- 如果无法将 变成 ,输出字符串
FIELDS MEDAL。
原题特别提示:输出区分大小写,字符串必须全部使用大写字母。输出中不要出现行首或行尾空格、连续两个空格或制表符。
样例
输入:
2
84 2 3 6
18588 3 18 25 44
输出:
3
4
样例说明
- 第一个测试用例的一种三步操作序列为 :依次除以素数 ,选择乘数 后加一,除以素数 。
- 第二个测试用例的一种四步操作序列为 :依次除以素数 ,选择乘数 后加一,选择乘数 后加一,除以素数 。