如何检查给定数字的形式是否为x^y？
我正在准备面试，遇到了这个问题：
编写一个程序，检查数字n是否为x^y形式。众所周知，n，x和y是整数，x和y大于2。
我想拿日志之类的东西，但不知道如何检查数字是否符合表格。你们谁能帮忙吗？：）
共有3个答案
有很多很好的答案，但我发现模算术仍然缺失。
根据要检查的数字的大小，按最后一位对它们进行分类可能会很有用。我们可以很容易地创建一个包含可能的候选对象的表。
为了展示它是如何工作的，让我们为最后4位创建这样一个表。在这种情况下，我们有16个案例需要考虑：
0^2, 0^3, ... : 0 mod 16
1^2, 1^3, ... : 1 mod 16
2^2, 2^3, ... : 0, 4, 8 mod 16
3^2, 3^3, ... : 9, 11, 1, 3 mod 16
4^2, 4^3, ... : 0 mod 16
5^2, 5^3, ... : 9, 13, 1, 5 mod 16
6^2, 6^3, ... : 4, 8, 0 mod 16
7^2, 7^3, ... : 1, 7 mod 16
8^2, 8^3, ... : 0 mod 16
9^2, 9^3, ... : 9, 1 mod 16
10^2,10^3, ... : 4, 8, 0 mod 16
11^2,11^3, ... : 9, 3, 1, 11 mod 16
12^2,12^3, ... : 0 mod 16
13^2,13^3, ... : 9, 5, 1, 13 mod 16
14^2,14^3, ... : 4, 8, 0 mod 16
15^2,15^3, ... : 1, 15 mod 16
相反，桌子更有用；对于给定的数字n=x^y，哪些基数x是可能的。
0: 0, 2, 4, 6, 8, 10, 12, 14 mod 16
1: 1, 3, 5, 7, 9, 11, 13, 15
2: -
3: 3, 11
4: 2, 6, 10, 14
5: 5, 13
6: -
7: 7
8: 2, 6, 10, 14
9: 3, 5, 9, 11, 13
10: -
11: 3, 11
12: -
13: 5, 13
14: -
15: 15
因此，只需查看四分之一数字的最后四位，就可以立即丢弃。
如果我们取数字13726423，它的16的余数是7，因此，如果它是我们感兴趣的形式，它必须是（16n7）^y。
对于大多数数字，要尝试的除数数量非常有限。在实践中，表可以我大得多，例如，16位。
二进制数的一个简单优化是去掉尾随的零。这使得不必担心偶数，并且y必须是除去的零的数量的因数。
如果我们仍然有太多的工作，我们可以创建另一个模表。另一个可以是，例如，模15。等效表如下所示：
0: 0
1: 1, 2, 4, 7, 8, 11, 13, 14
2: 2, 8
3: 3, 12
4: 2, 4, 7, 8, 13
5: 5
6: 3, 6, 9, 12
7: 7, 13
8: 2, 8
9: 3, 9, 12
10: 5, 10
11: 11
12: 3, 12
13: 7, 13
14: 14
由于前面示例（13726423）中的数字是13模15，那么x=（15 m 7）或（15 m 13）。由于15和16中没有公共因子，因此有效数字为240 p 7和240 p 103。通过两个整数分割和两个表查找，我们成功地将x的可能值限制为数字的1/120。
如果表格比较大，可能的x的数量很容易限制在一个非常低的数字。例如，对于65536和65535元素的表，循环是4294901760，因此对于大约1.6 x 10^19以下的任何数字，两个表给出了x的可能值的简短唯一列表。
解决这一问题的一种方法是分解n，计算各个因素，并找到计数的最大公分母。如果GCD为1，则答案为“否”。否则，答案是“是”。
以下是一些例子：
- 7，质因数7（一次）。我们有一个因素重复一次。回答否，因为GCD是1。
- 8，质因数2（3倍）。我们有一个因子，数到三。回答“是”，因为GCD是3。
- 144，质因数2（4倍）3（2倍）。4和2的GCD是2，所以答案是“是”。
- 72，质因数2（3倍）3（2倍）。3和2的GCD是1，所以答案是“否”。
“拿着日志和其他东西”是一条路。注意，N
这比@dasblinkenlight的解决方案快得多，后者要求您首先考虑N。（整数因式分解没有已知的多项式时间算法，即N位数的多项式。但是，小指数的整数幂运算可以在多项式时间内完成。）
-
问题内容： 下面的代码不适用于某些输入。 我最初的想法是检查每个输入是否为2的幂，方法是从1开始乘以2直到超过输入数量，然后在每个步骤进行比较。相反，我预先存储了2的所有幂，以便检查中的给定输入。如何改善呢？ 问题答案： 将 _ 最好的，最准确_ 的方法是使用位操作： 说明： 2的每个幂将1位恰好设置为1（该数的对数以2为底的索引中的位）。因此，当从中减去1时，该位翻转为0，而所有在前位翻转为
-
本文向大家介绍检查给定的四个点是否形成正方形，包括了检查给定的四个点是否形成正方形的使用技巧和注意事项，需要的朋友参考一下 在二维平面中，给出了四个点。该算法将检查四个点是否形成正方形。 检查正方形我们必须匹配这些条件- 给定点形成的所有四个边都相同。 所有两个连接侧都是直角的。 输入输出 算法 在此过程中，我们将使用方法squareDist(p1,p2)，它将返回两个给定点的平方距离。 输入：
-
问题内容： 我有一个小程序，允许用户输入一些正则表达式。之后，我想检查此输入是否为 有效的 正则表达式。 我想知道Java中是否有内置方法，但是找不到这种喷射器。 你能给我一些建议吗？ 问题答案： 这是一个例子。 然后输出，例如。
-
问题内容： 我只是在Firefox的JavaScript控制台中尝试过，但是以下任何语句都不返回true： 问题答案： 试试这个代码：
-
问题内容： 我想创建一个函数来接收输入字符串，该字符串可以是json格式的字符串，也可以只是一个字符串。例如，以下功能很简单。 问题答案： 我不清楚您是否仅需要了解“引号字符串”，还是需要了解json或两者之间的区别，因此，这向您展示了如何检测这两种情况，因此您可以非常具体。 我也在这里发布了交互式代码示例：http : //play.golang.org/p/VmT0BVBJZ7 将输出以下内容
-
本文向大家介绍编写Golang程序以检查给定数字是否为质数，包括了编写Golang程序以检查给定数字是否为质数的使用技巧和注意事项，需要的朋友参考一下 定义： 一个数字是大于2且只能被其自身和1整除。 示例：素 数是2、3、5、7、11、13、113、119等。 解决这个问题的方法 步骤1：找到给定数字的平方根sq_root =√num 步骤2：如果给定数字可被[2，sq_root]所属的数字整除