QOJ.ac

QOJ

実行時間制限: 10 s メモリ制限: 512 MB 満点: 100

#3833. 库尔特·哥德尔

統計

Kurt Friedrich Gödel 是一位奥地利数学家和哲学家。他受到过 Isaac Newton 和 Immanuel Kant 等前代科学家兼哲学家的影响,后来也影响了 Bertrand Russell 等数学家和哲学家。他在著名的“不完备性定理”的证明中利用了一种被称为哥德尔编码(Gödel numbering)的方法,该定理检验了数学和逻辑本身的边界与极限。这使他成为历史上与亚里士多德齐名的最重要的逻辑学家之一。

让我们看看这个哥德尔编码系统是如何工作的。它为每个符号分配一个数字,在本例中,我们使用大写字母(A 到 Z),并将它们分配给自然数 1 到 26。因此,A 被分配为 1,B 被分配为 2,依此类推。所以像 KURT 这样的单词将变成序列 $(11, 21, 18, 20)$。然后,我们将它表示为素数幂的乘积。序列 $(a_1, a_2, \dots, a_n)$ 应编码为 $2^{a_1} \cdot 3^{a_2} \cdot \dots \cdot p_n^{a_n}$,其中 $p_i$ 是第 $i$ 个素数。即,KURT 的哥德尔数是 $2^{11} \cdot 3^{21} \cdot 5^{18} \cdot 7^{20} = 6520744440162926921184290648437500000000000$。

长单词的哥德尔数可能非常大。你的朋友 Albert 想通过哥德尔数给你留下一条信息,但他懒得写出所有的数字。Albert 使用三元组 $(\ell, r, p)$ 来表示一个哥德尔数 $g$,其中 $\ell$ 是对应单词的长度,$p$ 是一个素数,且 $r \equiv g \pmod p$。然而,Albert 没有注意到两个不同的单词可能会生成相同的三元组。例如,EA 和 JA 的哥德尔数分别是 96 和 3072,但 Albert 可能会用 $(2, 3, 31)$ 来表示它们两者。让我们试着解码 Albert 的信息!

输入格式

最多有 30 组测试数据。每组测试数据占一行,包含三个整数。第一个整数 $\ell$ ($1 \le \ell \le 8$) 是单词的长度。第二个整数 $r$ 表示结果的余数。第三个整数 $p$ 是模运算中使用的素数。我们保证 $0 \le r < p < 2^{31}$。输入以三个零结束。

输出格式

如果生成该三元组的单词是唯一的,则输出该单词。如果存在多种可能性,则输出 “ambiguous”。如果不存在任何单词能产生该三元组,则输出 “not a word”。

样例

输入 1

1 2 3
3 11385 13339
7 123123123 2089141547
7 0 2089141547
0 0 0

输出 1

ambiguous
COW
ambiguous
not a word

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.