#P18535. Generalized Collatz Conjecture

Generalized Collatz Conjecture

Generalized Collatz Conjecture

你是一位满怀热情的本科生,看过一段关于 Collatz 猜想的 YouTube 视频对 Collatz 猜想做了深入研究,并灵光一现,想出了几个绝妙的解决办法!你已经开始想象:本科毕业论文将解决 Collatz 猜想,让你的名字与冯·诺伊曼、陶哲轩和拉马努金这样的天才一同写入教科书。导师认为这不是一个好主意,提醒你已有许多人尝试并失败。但他们不懂:别人是别人,你是你;这次不同,你是特别的。

由于你的坚持,导师勉强同意支持你,但条件是先解决下面这个比 Collatz 猜想的设定更困难、更一般的问题,以证明自己的能力。

给定一个由互不相同的整数组成的集合 MM 和整数 nn。你可以执行以下两种操作:

  1. 选择一个 m∈Mm\in M,将 nn 替换为 mn+1mn+1。
  2. 选择当前 nn 的一个素因子 pp,将 nn 替换为 n/pn/p。

求将 nn 变为 11 所需的最少操作次数。如果无法做到,也请报告。

输入格式

第一行包含测试用例数 tt。接下来有 tt 行,每行描述一个测试用例。

每行包含 2+∣M∣2+|M| 个以空格分隔的整数:前两个整数为 nn 和 ∣M∣|M|,接下来 ∣M∣|M| 个整数为集合 MM 的元素。

  • 1≤t≤2621441\le t\le262144。
  • 2≤n≤20971522\le n\le2097152。
  • 1≤∣M∣≤81\le |M|\le8。
  • 对每个 m∈Mm\in M,1≤m≤641\le m\le64。
  • 同一输入文件中,没有两个测试用例完全相同,即不存在重复的 (n,M)(n,M)。
  • MM 的元素按严格递增顺序给出。

输出格式

对每个测试用例输出一行,包含以下两者之一:

  • 将 nn 变成 11 所需的最少操作次数,输出一个整数;
  • 如果无法将 nn 变成 11,输出字符串 FIELDS MEDAL。

原题特别提示:输出区分大小写,字符串必须全部使用大写字母。输出中不要出现行首或行尾空格、连续两个空格或制表符。

样例

输入:

2
84 2 3 6
18588 3 18 25 44

输出:

3
4

样例说明

  • 第一个测试用例的一种三步操作序列为 84→12→37→184\to12\to37\to1:依次除以素数 77,选择乘数 33 后加一,除以素数 3737。
  • 第二个测试用例的一种四步操作序列为 18588→12→301→5419→118588\to12\to301\to5419\to1:依次除以素数 15491549,选择乘数 2525 后加一,选择乘数 1818 后加一,除以素数 54195419。