问题标签 [number-theory]

我正在实现算法的以下步骤，我已经成功实现了前 3 个步骤，我对最后一步有疑问，我无法理解用于表示散列函数的符号，我究竟需要传递什么作为参数是下面给出的哈希函数（最后一步）。提前致谢。

任何人都能想到的最有效的算法是什么，给定一个自然数n，返回具有n 个正除数（包括 1 和x ）的最小自然数x？例如，给定 4，算法应该得到 6（除数：1,2,3,6）；即 6 是具有 4 个不同因子的最小数字。同样，给定 6，算法应该得到 12（除数：1、2、3、4、6、12）；即 12 是具有 6 个不同因子的最小数字

就实际性能而言，我正在寻找一种可扩展的算法，它可以在每秒可以进行 10 ⁷次计算的机器上在 2 秒内给出 10 ^{20量级的答案。}

我们正在寻找一种算法来在 O(N) 下解决这个问题。

给定两个实数 a 和 b（不失一般性，您可以假设它们都在 0 和 1 之间）找到一个介于 -N 和 N 之间的整数 n 以最小化表达式：

|an - b - 圆形(an - b)|

我们认为欧几里得算法可能适用于此，但无法弄清楚。看起来应该有比通过对整数 n 进行详尽搜索更快的方法来做到这一点。

注意：在我们的情况下，a 和 b 可能会经常变化，因此可以为查找表修复 a 和 b，它会变得有点难看，因为 N 也可以变化。还没有详细查看查找表，看看我们可以将它作为 N 的函数得到多小。

我有两个数字，x1和x2。对于一个数字y，我想计算x1和x2尽可能接近的公约数y。

有没有一个有效的算法呢？

我相信是时候重新表述我的问题并更清楚了。这与整数无关......所以，假设我们有两个数字x1和x2。比如说，用户输入了一个数字y。我想要找到的是一个y'接近的数字y，x1 % y'并且非常小（例如，x2 % y'小于，但让我们称之为这个数字）。换句话说，我不需要一个最佳算法，而是一个很好的近似值。0.02LIMIT

我感谢大家的时间和精力，真是太好了！

欧拉计划的第十个问题：

10以下的素数之和为2 + 3 + 5 + 7 = 17。

求两百万以下的所有素数之和。

我发现了这个片段：

在此处发布 ，运行 3 秒。

我写了这段代码：

我不明白为什么我的代码（第二个）要慢得多？

在开始之前让我说：这不是家庭作业，只是简单、古老、有趣。

现在，我正在尝试提出一个可以回答这个问题的算法1/x + 1/y = 1/n！.

正如您在上面的链接中看到的那样，作者只要求提示而不是实际答案，所以我也很乐意提出同样的要求。

我简化了表达式，直到 (x - n!)(y - n!) = (n!)^2 正如其中一个答案所建议的那样，到那时我才明白 (x,y) 对的组合数与 n!^2 的除数相同（如果我在这里错了，请纠正我）。

因此，正如接受的答案所建议的那样，我试图得到构成 N!^2 的每个素数的所有因子的乘法。

我用 C 语言编写了一些代码，使用试除法分解 N!^2 和Eratosthenes 的筛子，使所有素数达到 sqrt(N!^2)。

现在的问题是内存，我尝试过使用 N = 15，而我的 Mac（四核 6GB 内存）几乎死在我身上。问题是记忆。所以我添加了一些 printf 并尝试使用 N=11：

该列表是 N!^2 的所有主要因素（当然除了 1 和 N!^2）。

我想要一些关于如何最小化内存消耗和可能的优化的提示。

下面的代码，这只是一个快速的实验，所以我相信它可以被优化。

编辑：

作为一个例子，我将向您展示获得初始方程的所有可能正整数解的计算：

3!^2 = 36 = (3^2*2^2*1^0)

所以丢番图方程有 (1+2)(1+2)(1+0)=9 个可能的正整数解。如果计算负整数，则加倍。可以肯定的是，我正在使用WolframAlpha 。

编辑2：

我想我刚刚发现“什么是阶乘”，我得到了这个非常有趣的输出：

感谢：D

我正在练习 ACM ICPC 过去的问题http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030

我无法解决这个问题，并且完全不知道如何在 3 秒的时间限制内以有效的方式做到这一点。我认为这个问题是基于数论的，但不知道该怎么做。谢谢！

找到十个整数>0，总和为 2011，但它们的倒数总和为 1

例如

x1+x2+..+x10 = 2011

1/x1+1/x2+..+1/x10 = 1

我在这里发现了这个问题http://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html

我想知道计算复杂度是多少，什么类型的算法可以解决它。

EDIT2：我编写了以下足够快的蛮力代码。我没有找到任何解决方案，所以我需要稍微调整一下我的假设。我现在有信心找到解决办法。

我需要帮助找出解决这个问题的更好方法（可能是一个更数学的方法！）。以下是详细信息：

问题陈述：

给定 N 和 M，您需要找出有多少对 a,b (1 <= a < b <=N) 使得 (a+b) 可以被 M 整除。例如，当 N=4 和 M=3 ，有 2 个可能的对，它们的总和可以被 M 整除，它们是 (1,2) 和 (2,4)。

约束：1 <= N <= 10^9 和 2 <= M <= 10^9。 时间限制：1秒

在我的算法中，我循环了 N 次，使其成为 O(N) 算法。这是代码：

我只是检查在 (2a,n+a) 范围内有多少数可以被 M 整除，其中 1 =< a < n。如果您查看范围内所有(a,b)的总和，您就会知道我为什么选择(2a,n+a)。

然而，这种O(N)方法并不是很快。对于 N=10 ⁹和 M=2，程序在 12 秒内将答案打印为 249999999500000000，这非常慢。还可以使用哪些其他方法？我想不出更好的方法。请帮忙！

我们在一门大学课程中学习了 MASH-2 哈希函数，在考试中我们遇到了仅使用科学计算器计算类似 ((62500)^257)) mod (238194151) 的问题。现在我知道一些关于 a^b (mod n) 的理论，但我上面提出的问题甚至很难手动计算。我认为解决这个问题大约需要 15 分钟。我想知道是否有更快的方法来做到这一点。或者即使有某种方法可以以二进制形式进行（将数字转换为二进制，然后进行一些操作）。我需要能够用科学计算器手动完成。