Brendan
2020-01-31 16:52
让我们来研究这个问题：
给定数字x，您的任务是找到第一个自然数i，其阶乘数可被x整除。
也就是说，找到n这样n! % x == 0。
如果拆分n!并x为他们的主要因素（如像“60 = 2 * 2 * 3 * 5”）你知道，其余的将是零，当所有的主要因素，x也是首要因素n!; 这意味着n必须等于或大于的最大素数x。
在最坏的情况下，如果x为素数（只有一个素数），则n必须等于x。例如，如果x为61，n则将为61。这很重要，因为它n!很快变大并会溢出（例如，61!不能容纳64位）。
幸好; 如果n大于2；n!与相同(n-1)! * n; 并且((n-1)! * n) % x与相同((n-1)! % x) * n) % x。
换一种说法; 为了使其工作（避免溢出），您可以执行以下操作（无需进行任何计算n!）：
do {
i = i + 1;
remainder = remainder * i;
remainder = remainder % x;
while(remainder != 0);
现在...
假设选择x不会发生溢出。
这实际上是什么意思？
如果询问代码的人认为您将使用我描述的算法；那么它可能意味着x将小于1 << 64的平方根）；因此，如果您使用“更可能发生溢出的算法”（任何会计算的值的算法），那么就会产生溢出，n!因此必须使用我的算法（或找到更好的算法）。
任何状况之下; 递归是不好的，也是不必要的。
热门帖子
10
相关问题
热门github
1
2
4
The Python Risk Identification Tool for generative AI (PyRIT) is an open access automation framework to empower security professionals and machine learning engineers to proactively find risks in their generative AI systems.
(翻译：用于生成式 AI 的 Python 风险识别工具 (PyRIT) 是一个开放式访问自动化框架，使安全专业人员和机器学习工程师能够主动发现其生成式 AI 系统中的风险。)
5
7
8
9
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.
(翻译：Mamba 是一种新的状态空间模型架构，在信息密集型数据（例如语言建模）上显示出良好的性能，而之前的二次模型在 Transformers 方面存在不足。它基于结构化状态空间模型的进展，并本着FlashAttention的精神进行高效的硬件感知设计和实现。)
10
11
13