问题标签 [number-theory]

我正在尝试找到解决方案的数量

其中 b<=50 但 a 和 u 可以很大。我的方法是从 0 到 min(b,u) 遍历 x 的每个值，如果它满足等式添加 ceil((ux)/b) （以说明 x 的值的数量大于 b但在 b) 的乘法域中等价于解的数量。我不确定我的算法的正确性。我可以将我的方法扩展到多个变量，例如是否存在

我可以生成所有无序的 x 和 y 对，使得 x<=y 直到 (x,y)<=min(b,u) 并再次计算 i=ceil((ux)/b) 和 j=ceil((uy )/b) 并将总和相乘为：

并对 t 求和。我想知道我的算法是否正确以及是否有其他更有效的算法。

我试图解决http://poj.org/problem?id=1426 (2002 dhaka region) 。虽然我无法提出所需的确切算法，但由于 n 从 1 到 200 不等，我通过生成二进制数和检查可分性来预先计算所有值。现在我有一个恒定时间算法:) 但我确信这不是解决问题的正确方法。我不想使用图形搜索算法，因为这个问题属于网站的基本数学，所以我认为这个问题必须有一个数学解决方案，它不会给出 TLE。

我当前用于计算 Legendre 符号的代码是

这里可以进行任何优化吗？

找出一个数字的除数的最优化方法是什么，使得除数中至少有数字 3？

例如 21=1,3,7,21

因此只有一个除数中有数字 3。

例如 62=1,2,31,62

因此只有一个除数中有数字 3，即 31

编辑-我意识到最好的方法是找出一个数字的所有因数并检查包含数字 3 的因数。

找出因素的最佳方法：

获取数字的因数

获得一个数字的所有除数的最佳方法是什么？

我最近在休息时间一直在玩 HackerRank，在解决这个问题时遇到了一些麻烦：https ://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers有效。

问题陈述：给定两个整数X和N，找出表示为唯一自然数X的幂和的方式数。N

示例： X = 10，N = 2

只有一种方法可以使用 10 以下的2的幂得到 10 ，那就是1^2 + 3^2

我的方法

我知道这个问题可能存在一个很好的、优雅的重现；但不幸的是我找不到，所以我开始考虑其他方法。我决定收集一系列数字，[1,Z]其中Z是小于X的最大数字，当提升到N次方时。所以对于上面的例子，我只考虑[1,2,3]因为4^2 > 10，因此不能是总和为 10 的（正）数字的一部分。在收集了这个数字范围后，我将它们全部提升到N次方，然后找到所有子集的排列这个清单。所以[1,2,3]我发现[[1],[4],[9],[1,4],[1,9],[4,9],[1,4,9]]，而不是针对大初始数字范围的一系列操作（我的解决方案在最后两个hackerrank测试中超时）。最后一步是计算总和为X的子列表。

解决方案

有没有人遇到过这个问题？如果是这样，是否有更优雅的解决方案？

下面的代码片段检查给定数字是否为质数。有人可以向我解释为什么会这样吗？这段代码在给我们的 Java 考试学习指南中。

计算满足方程的第一个 n 的最快方法是什么

a^n 模 m = 1

这里 a,n,m 可以是素数或复合模：是模运算符

我编写了以下代码来计算 n！模 p...鉴于 n 和 p 很接近...但它以一种相当有趣的方式运行，无法找出错误..某处有一些溢出..约束是1 < P <= 2*10^9

1 <= N <= 2*10^9 虽然它在少数情况下运行良好......可能是什么错误。我用过

和p素数一样……和威尔逊定理(p-1)! mod p = p-1

一个集合的 Frobenius 数存在当且仅当该集合数的 gcd 为 1。给定一组最多有 10 个元素的正整数，使得所有元素的 gcd 为 1，我们如何计算该集合的 Frobenius 数?

这是原始问题的链接：https ://icpcarchive.ecs.baylor.edu/external/62/6298.pdf Sylvester 的公式可用于查找一组 2 个元素的 Frobenius 数。

在回答另一个问题时，我偶然发现了一个问题，即在没有Symbolic Math Toolbox的情况下，我实际上如何能找到整数的所有因数。

例如：

返回：

因此将返回所有素因子，“1”缺失。

而且我正在寻找一个可以返回所有因素的函数（1和数字本身并不重要，但它们会很好）

预期输出x = 60：

我想出了那个相当庞大的解决方案，除了它可能可以被矢量化，没有任何优雅的解决方案吗？

另外我认为，对于某些大数字，此解决方案将失败，因为 perms 需要矢量长度<11。