问题标签 [number-theory]

你怎么能用模余数做除法？

例如：求 9^2012 除以 11 的余数。

使用模运算，9 == 1(mod 4)，所以 9^2012 == 1^2012(mod 4)。因此，9^2012 == 1(mod 4)。此外，11 == 3（模 4）。为了回答这个问题，我正在尝试做 1(mod 4)/3(mod 4)。有没有办法做到这一点？

我有一些（比如说，n）弹珠（小玻璃球），我打算买一些盒子来存放它们。盒子有两种：

我希望每个用过的盒子都能装满它的容量，并尽量减少购买它们的总成本。由于我很难弄清楚如何在盒子之间分配弹珠，因此我寻求您的帮助。我希望你的程序也高效。

输入文件可能包含多个测试用例。每个测试用例都以包含整数 n (1 <= n <= 2,000,000,000) 的行开始。第二行包含 c1 和 n1，第三行包含 c2 和 n2。这里，c1、c2、n1和n2都是小于2,000,000,000的正整数。

第一行中 n 为零的测试用例终止输入。

对于输入中的每个测试用例，打印一行包含最小成本解决方案（两个非负整数 m1 和 m2，其中 mi = 所需的类型 i 框的数量），如果存在，则打印“失败”。

如果存在解决方案，您可以假设它是唯一的。

The code below works perfectly but I would like someone to explain to me the mathematics behind it. Basically, how does it work?

我想知道下面解释的任务在理论上是否可行，如果可以，我该怎么做。

给定一个N元素空间（即 和 之间的所有数字0。N-1）让我们看看该空间上所有排列的空间，并将其称为S。的i第 th 个成员S，可以被标记S[i]，是带有字典序号的排列i。

例如，如果N是 3，那么S是这个排列列表：

（当然，当看一个 big 时N，这个空间变得非常大，N!确切地说。）

现在，我已经知道如何通过索引号获取排列i，并且我已经知道如何进行相反的操作（获取给定排列的字典序号。）但我想要更好的东西。

一些排列本身可能是巨大的。例如，如果您正在查看N=10^20. （S我(10^20)!认为这是我在 Stack Overflow 问题中提到的最大数字：）

如果您只是查看该空间上的随机排列，那么它会太大以至于您无法将整个内容存储在硬盘上，更不用说按字典序号计算每个项目了。我想要的是能够对该排列进行项目访问，并获得每个项目的索引。也就是说，给定N并i指定一个排列，有一个函数接受一个索引号并找到驻留在该索引中的数字，另一个函数接受一个数字并找到它所在的索引。我想在 中执行此操作O(1)，因此我不需要存储或迭代排列中的每个成员。

疯了，你说？不可能的？那可能。但是考虑一下：像 AES 一样的分组密码本质上是一种排列，它几乎可以完成我上面概述的任务。AES 的块大小为 16 字节，这意味着N大约. （无关紧要的大小是一个惊人的，或大约，这超过了我最近的“堆栈溢出中提到的最大数字”的记录：）256^1610^38S(256^16)!10^85070591730234615865843651857942052838

每个 AES 加密密钥在N=256^16. 这种排列不能完整地存储在你的计算机上，因为它的成员比太阳系中的原子还多。但是，它允许您访问项目。通过使用 AES 加密数据，您可以逐块查看数据，并且对于每个块（的成员range(N)）输出加密块，该加密块的成员range(N)位于排列中原始块的索引号中。当你解密时，你正在做相反的事情（查找一个块的索引号。）我相信这是在 中完成的O(1)，我不确定，但无论如何它非常快。

使用 AES 或任何其他分组密码的问题在于它将您限制在非常具体的范围内N，并且它可能只捕获一小部分可能的排列，而我希望能够使用任何N我喜欢的，并在任何我喜欢的排列S[i]。

是否可以在给定大小和排列数O(1)的排列上获得项目访问权限？如果是这样，怎么做？Ni

（如果我有幸在这里得到代码答案，如果他们会在 Python 中，我将不胜感激。）

更新：

一些人指出了一个可悲的事实，即排列数字本身会如此巨大，以至于仅读取数字会使任务不可行。然后，我想修改我的问题：如果可以访问排列的字典序数的阶乘表示，是否有可能在 O 中获得排列中的任何项目（尽可能小）？

I'm new to Prolog. I read this code which finds prime factors of an integer:

And changed it to this one:

Well the first one works perfect, but the latter doesn't respond to queries. i.e. when I enter:

I get 'true', but when I enter:

I get 'false'.

如果我有点傻，请原谅我，但我最近才开始编程，在 Project Euler 上做问题 160 可能有点超出我的深度。我已经尝试解决它，但似乎在任何个人计算机上处​​理 1tn 数字都需要很长时间，所以我想我应该研究数学以找到一些捷径。

欧拉计划问题 160：

对于任何 N，令 f(N) 为 N! 中尾随零之前的最后五位数字。例如，

9！= 362880 所以 f(9)=36288 10！= 3628800 所以 f(10)=36288 20！= 2432902008176640000 所以 f(20)=17664

求 f(1,000,000,000,000)

新尝试：

旧尝试：

我尝试实施 Lehmann 测试，但它第一次不起作用。我按照每个人的描述

1. 计算 r = [ a^( (p -1) / 2) ] mod p
2. 如果 r 不是 1 或 –1，那么 p 肯定不是素数。
3. 如果 r = 1 或 –1，p 不是素数的可能性最多为 50%。

不管我怎么做，它永远不会奏效。我什至尝试过硬编码

f 最终为 6

任何帮助将不胜感激

问题：http ://www.spoj.com/problems/DIVREL

有问题的是，我们只需要从给定的一组元素中找到最大数量的元素不是倍数（a 可以被 b 整除）。如果我们只是从一个元素到它的倍数创建一条边并构建一个图，它将是一个 DAG。

现在问题变成了使用Dilworth 定理找到包含等于反链基数的所有顶点的最小链数，因为它是一个部分有序的集合。

可以使用二分匹配找到最小链（如何：它是最小路径覆盖）但现在我无法找到反链元素本身？

我想将一堆图像调整得非常小，以便我可以对它们进行一些图像分析。我希望它们都包含相同数量的像素以进行矢量比较。我选择了“120”，因为它是高度复合的。我可以将每张图像的大小调整为 12x10，但是对于没有 1.2 纵横比的图像，可能会出现不必要的拉伸。

如何选择最接近原始纵横比的新宽度和高度？

作为参考，120 的除数是：{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}，因此有效尺寸为 12x10， 10x12、8x15、15x8、6x20、20x6 等等。

编辑： 144 可能是一个更好的选择，因为它允许方形图像和流行的 16:9 比例。

我在 Maxima 中定义了一个扩展的欧几里得算法

为了解决a + b = c形式的线性丢番图方程，其中gcd（a，b）= 1，但是如果ab = c我得到-1由除数算法返回，但gcd（a，-b）为前。我的算法是错误的，还是可以用于 ab=c？

伊恩