当前位置： 文江博客 话题详情

如何处理和理解与数学相关的DSA问题

发布于 2025-02-09 03:19:24 字数 529 浏览 2 评论 0 原文

我在网上发现了这个问题，我真的不知道这个问题是什么问题。我真的很感谢您在首先理解这个问题时提供一些帮助，并在可能的情况下进行解决方案。谢谢！

要查看一个数字是否可以按3分组，您需要添加其十进制符号的数字，并检查总和是否可除以3。 要查看一个数字是否可以除以11，您需要将其十进制符号拆分为一对数字（从右端开始），添加相应的数字，并检查总和是否可除以11。

对于任何prime P（2和5除外），存在一个整数r，因此存在类似的可驱缘性测试：要检查一个数字是否可以按P进行分组，您需要将其十进制表示法拆分为数字的r-tuplace （从右端开始），添加这些R-tupers，然后检查其总和是否可以除以p。

给定一个prime int p，找到该划分性测试有效并输出的最小R。

输入由单个整数P- 3和999983之间的素数组成，包含在内，不等于5。

示例

输入

3

输出

1

输入

11

输出

2

原文

I found this question online and I really have no idea what the question is even asking. I would really appreciate some help in first understanding the question, and a solution if possible. Thanks!

To see if a number is divisible by 3, you need to add up the digits of its decimal notation, and check if the sum is divisible by 3.
To see if a number is divisible by 11, you need to split its decimal notation into pairs of digits (starting from the right end), add up corresponding numbers and check if the sum is divisible by 11.

For any prime p (except for 2 and 5) there exists an integer r such that a similar divisibility test exists: to check if a number is divisible by p, you need to split its decimal notation into r-tuples of digits (starting from the right end), add up these r-tuples and check whether their sum is divisible by p.

Given a prime int p, find the minimal r for which such divisibility test is valid and output it.

The input consists of a single integer p - a prime between 3 and 999983, inclusive, not equal to 5.

Example

input

3

output

1

input

11

output

2

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（4）

花期渐远 2025-02-16 03:19:24

这是一个非常酷的问题！它使用模块化算术和一些基本数字理论来设计解决方案。

假设我们有 p = 11 。这里适用哪种可驱缘性规则？我们需要立即获得多少位数字，以制定可驱缘性规则？

好吧，让我们一次尝试一个数字。这意味着，如果我们拥有 121 ，并且我们总和其数字 1 + 2 + 1 ，那么我们获得 4 。但是，我们看到的是，尽管 121 可以通过 11 ， 4 不可行，因此该规则不起作用。

如果我们一次拿两位数怎么办？使用 121 我们获得 1 + 21 = 22 。我们看到 22 是由 11 排除，因此该规则可能在这里工作。实际上，确实如此。对于 p = 11 ，我们有 r = 2 。

这需要一些我无法在文本中传达的直觉（我真的已经尝试过），但是可以证明，对于给定的Prime P ，除 2 和<代码> 5 ，划分规则适用于长度的数字 r 时，仅当数字 99 ... 99 ... 9 （带有 r） nines）可以通过 p 将其排除。实际上，对于 p = 3 我们有 9％3 = 0 ，而对于 p = 11 我们有 9％11 = 9 （这是不好的）和 99％11 = 0 （这是我们想要的）。

如果我们想找到这样的 r ，我们以 r = 1 开始。我们检查 9 是否可以通过 p 将其排除。如果是，那么我们找到了 r 。否则，我们走得更远，我们检查 99 是否可以通过 p 将其排除。如果是，那么我们返回 r = 2 。然后，我们检查 999 是否由 p 排除，如果是，则返回 r = 3 等等。但是， 99 ... 9 数字可能会变得很大。值得庆幸的是，要通过 p 检查可划分性，我们只需要存储剩余的modulo p ，我们知道它很小（至少小于 999983 ） 。因此，C ++中的代码看起来像这样：

int r(int p) {
  int result = 1;
  int remainder = 9 % p;
  while (remainder != 0) {
    remainder = (remainder * 10 + 9) % p;
    result++;
  }
  return result;
}

This is a very cool problem! It uses modular arithmetic and some basic number theory to devise the solution.

Let's say we have p = 11. What divisibility rule applies here? How many digits at once do we need to take, to have a divisibility rule?

Well, let's try a single digit at a time. That would mean, that if we have 121 and we sum its digits 1 + 2 + 1, then we get 4. However we see, that although 121 is divisible by 11, 4 isn't and so the rule doesn't work.

What if we take two digits at a time? With 121 we get 1 + 21 = 22. We see that 22 IS divisible by 11, so the rule might work here. And in fact, it does. For p = 11, we have r = 2.

This requires a bit of intuition which I am unable to convey in text (I really have tried) but it can be proven that for a given prime p other than 2 and 5, the divisibility rule works for tuples of digits of length r if and only if the number 99...9 (with r nines) is divisible by p. And indeed, for p = 3 we have 9 % 3 = 0, while for p = 11 we have 9 % 11 = 9 (this is bad) and 99 % 11 = 0 (this is what we want).

If we want to find such an r, we start with r = 1. We check if 9 is divisible by p. If it is, then we found the r. Otherwise, we go further and we check if 99 is divisible by p. If it is, then we return r = 2. Then, we check if 999 is divisible by p and if so, return r = 3 and so on. However, the 99...9 numbers can get very large. Thankfully, to check divisibility by p we only need to store the remainder modulo p, which we know is small (at least smaller than 999983). So the code in C++ would look something like this:

int r(int p) {
  int result = 1;
  int remainder = 9 % p;
  while (remainder != 0) {
    remainder = (remainder * 10 + 9) % p;
    result++;
  }
  return result;
}
回复 原文
彼岸花似海 2025-02-16 03:19:24

我不知道他们如何期望一个没有背景的随机程序员可以从中找出答案。

但是，这是对Modulo算术的简要介绍，应该使此问题可行。

在编程中， n％k 是Modulo操作员。它是指 n / k < / code>的其余部分。它满足以下两个重要属性：

(n + m) % k = ((n % k) + (m % k)) % k
(n * m) % k = ((n % k) * (m % k)) % k

因此，对于任何 k ，我们都可以考虑所有数字，其余的数字与以某种方式相同。结果是称为“整数Modulo k ”。它满足了您习惯的大多数代数规则。您拥有关联属性，交换性属性，分配定律，添加0，而乘法乘以1

。事实 2 * 5 = 10 这意味着Modulo 10 ， 2 * 5 = 0 。这是分裂的问题。

但是，如果 k = p ，一个素数，那么事情变得非常容易。如果（a *m）％p =（b *m）％p ，则（（AB） *m）％p = 0 so （ab） * M 可以通过 p 将其排除。因此，要么（AB）或 m 可以通过 p 将其排除。

对于任何非零剩余 m ，让我们看一下序列 m％p，m^2％p，m^3％p，... 。该序列无限长，只能播放 p 值。因此，我们必须在 a＆lt的地方重复； b 和 m^a％p = m^b％p 。因此（1 * m^a）％p =（m^（ba） * m^a）％p 。由于 m 不划分 p ， m^a 也不会1 。此外， m^（ba-1）％p 像 m^（-1）= 1/m 一样行动。 （如果您拿了足够的数学，您会发现在乘法下的非零剩余物是有限的组，所有剩余的人都会形成一个字段。但是，让我们忽略这一点。

） 存在。

p 到处都有任何计算中都 然后 1，m，m^2，...，m^（a-1）形成一个长度 a 的周期。对于任何 n 在 1中，...，P-1 我们可以形成一个周期（可能相同，可能不同） n，n*m，n *m^2，...，n*m^（a-1）。可以证明，这些周期分区 1，2，...，P-1 每个数字都在一个周期中，每个周期都有长度 a 。因此， a 除以 p-1 。附带说明，由于 除以 p-1 ，我们很容易获得 fermat的小定理 m^（p-1）具有剩余 1 ，因此 m^p = m 。

好的，足够的理论。现在解决您的问题。假设我们有一个基本 b = 10^i 。他们正在讨论的原始测试是 a_0 + a_1 * b + a_2 * b^2 + a_k * b^k 在prime p 时都可以在 a_0 + a_1 + ... + a_k 可以通过 p 将其排除。查看（P-1） + B ，只有 b％p 为1。然后，在Modulo算术中 b 对任何功率均为 1 ，并且测试起作用。

因此，我们正在寻找最小的 i ，以便 10^i％p 是 1 。根据我上面显示的内容， i 始终存在，并划分 p-1 。因此，您只需要因素 p-1 ，然后尝试 10 对每个功率，直到找到有效的最小 i 。

请注意，您应该在每个步骤中％p ，以防止这些功率变得太大。并且通过重复的平方，您可以加快计算加速。因此，例如，可以通过依次计算以下每个过程来计算 10^20％p 。

10 % p
10^2 % p
10^4 % p
10^5 % p
10^10 % p
10^20 % p

I have no idea how they expect a random programmer with no background to figure out the answer from this.

But here is the brief introduction to modulo arithmetic that should make this doable.

In programming, n % k is the modulo operator. It refers to taking the remainder of n / k. It satisfies the following two important properties:

(n + m) % k = ((n % k) + (m % k)) % k
(n * m) % k = ((n % k) * (m % k)) % k

Because of this, for any k we can think of all numbers with the same remainder as somehow being the same. The result is something called "the integers modulo k". And it satisfies most of the rules of algebra that you're used to. You have the associative property, the commutative property, distributive law, addition by 0, and multiplication by 1.

However if k is a composite number like 10, you have the unfortunate fact that 2 * 5 = 10 which means that modulo 10, 2 * 5 = 0. That's kind of a problem for division.

BUT if k = p, a prime, then things become massively easier. If (a*m) % p = (b*m) % p then ((a-b) * m) % p = 0 so (a-b) * m is divisible by p. And therefore either (a-b) or m is divisible by p.

For any non-zero remainder m, let's look at the sequence m % p, m^2 % p, m^3 % p, .... This sequence is infinitely long and can only take on p values. So we must have a repeat where, a < b and m^a % p = m^b %p. So (1 * m^a) % p = (m^(b-a) * m^a) % p. Since m doesn't divide p, m^a doesn't either, and therefore m^(b-a) % p = 1. Furthermore m^(b-a-1) % p acts just like m^(-1) = 1/m. (If you take enough math, you'll find that the non-zero remainders under multiplication is a finite group, and all the remainders forms a field. But let's ignore that.)

(I'm going to drop the % p everywhere. Just assume it is there in any calculation.)

Now let's let a be the smallest positive number such that m^a = 1. Then 1, m, m^2, ..., m^(a-1) forms a cycle of length a. For any n in 1, ..., p-1 we can form a cycle (possibly the same, possibly different) n, n*m, n*m^2, ..., n*m^(a-1). It can be shown that these cycles partition 1, 2, ..., p-1 where every number is in a cycle, and each cycle has length a. THEREFORE, a divides p-1. As a side note, since a divides p-1, we easily get Fermat's little theorem that m^(p-1) has remainder 1 and therefore m^p = m.

OK, enough theory. Now to your problem. Suppose we have a base b = 10^i. The primality test that they are discussing is that a_0 + a_1 * b + a_2 * b^2 + a_k * b^k is divisible by a prime p if and only if a_0 + a_1 + ... + a_k is divisible by p. Looking at (p-1) + b, this can only happen if b % p is 1. And if b % p is 1, then in modulo arithmetic b to any power is 1, and the test works.

So we're looking for the smallest i such that 10^i % p is 1. From what I showed above, i always exists, and divides p-1. So you just need to factor p-1, and try 10 to each power until you find the smallest i that works.

Note that you should % p at every step you can to keep those powers from getting too big. And with repeated squaring you can speed up the calculation. So, for example, calculating 10^20 % p could be done by calculating each of the following in turn.

10 % p
10^2 % p
10^4 % p
10^5 % p
10^10 % p
10^20 % p
回复 原文
恬淡成诗 2025-02-16 03:19:24

这几乎是 fermat的小定理的几乎直接应用。

首先，您必须重新将重新重新调整为“分组”元素[...]” 的条件为您可以使用的东西：

要检查一个数字是否可以除以p，您需要将其十进制表示法拆分为r-tupers（从右端开始），添加这些r-tuples，并检查其总和是否可除以p < /p>

翻译时是否可以由P除外。从散文到一个公式，它实际上说的是您想要

​代码> {0，...，10^r -1} （只有有限的许多 b_i 是非零）。

服用 b_1 = 1 和所有其他 b_i = 0 ，很容易看到

​也足够（左侧的所有 10^ri 只需转换为 1 ，无助于）。

现在，如果 p 既不是 2 也不是 5 ，则 10 将无法通过 p <可以分开/code>，以便fermat的小定理可以确保我们

​虽然这可能不是最小的 r ，而计算最小的一个很难，如果您不适合t有一个量子计算机方便。

尽管总体上很难，但对于非常小的 p ，您可以简单地使用 p 中的线性算法（您只需查看序列

10    mod p 
100   mod p
1000  mod p
10000 mod p
...

，然后立即停止找到等于 1 mod p 的东西。

例如，在Scala中写出作为代码：

def blockSize(p: Int, n: Int = 10, r: Int = 1): Int =
  if n % p == 1 then r else blockSize(p, n * 10 % p, r + 1)

println(blockSize(3))  // 1
println(blockSize(11)) // 2
println(blockSize(19)) // 18

或在Python中：

def blockSize(p: int, n: int = 10, r: int = 1) -> int:
  return r if n % p == 1 else blockSize(p, n * 10 % p, r + 1)

print(blockSize(3))  # 1
print(blockSize(11)) # 2
print(blockSize(19)) # 18

数字墙，以防万一其他人想知道理智 - 替代方法：

11 -> 2
13 -> 6
17 -> 16
19 -> 18
23 -> 22
29 -> 28
31 -> 15
37 -> 3
41 -> 5
43 -> 21
47 -> 46
53 -> 13
59 -> 58
61 -> 60
67 -> 33
71 -> 35
73 -> 8
79 -> 13
83 -> 41
89 -> 44
97 -> 96
101 -> 4
103 -> 34
107 -> 53
109 -> 108
113 -> 112
127 -> 42
131 -> 130
137 -> 8
139 -> 46
149 -> 148
151 -> 75
157 -> 78
163 -> 81
167 -> 166
173 -> 43
179 -> 178
181 -> 180
191 -> 95
193 -> 192
197 -> 98
199 -> 99

This is an almost direct application of Fermat's little theorem.

First, you have to reformulate the "split decimal notation into tuples [...]"-condition into something you can work with:

to check if a number is divisible by p, you need to split its decimal notation into r-tuples of digits (starting from the right end), add up these r-tuples and check whether their sum is divisible by p

When you translate it from prose into a formula, what it essentially says is that you want

enter image description here

for any choice of "r-tuples of digits" b_i from { 0, ..., 10^r - 1 } (with only finitely many b_i being non-zero).

Taking b_1 = 1 and all other b_i = 0, it's easy to see that it is necessary that

enter image description here

It's even easier to see that this is also sufficient (all 10^ri on the left hand side simply transform into factor 1 that does nothing).

Now, if p is neither 2 nor 5, then 10 will not be divisible by p, so that Fermat's little theorem guarantees us that

enter image description here

, that is, at least the solution r = p - 1 exists. This might not be the smallest such r though, and computing the smallest one is hard if you don't have a quantum computer handy.

Despite it being hard in general, for very small p, you can simply use an algorithm that is linear in p (you simply look at the sequence

10    mod p 
100   mod p
1000  mod p
10000 mod p
...

and stop as soon as you find something that equals 1 mod p).

Written out as code, for example, in Scala:

def blockSize(p: Int, n: Int = 10, r: Int = 1): Int =
  if n % p == 1 then r else blockSize(p, n * 10 % p, r + 1)

println(blockSize(3))  // 1
println(blockSize(11)) // 2
println(blockSize(19)) // 18

or in Python:

def blockSize(p: int, n: int = 10, r: int = 1) -> int:
  return r if n % p == 1 else blockSize(p, n * 10 % p, r + 1)

print(blockSize(3))  # 1
print(blockSize(11)) # 2
print(blockSize(19)) # 18

A wall of numbers, just in case someone else wants to sanity-check alternative approaches:

11 -> 2
13 -> 6
17 -> 16
19 -> 18
23 -> 22
29 -> 28
31 -> 15
37 -> 3
41 -> 5
43 -> 21
47 -> 46
53 -> 13
59 -> 58
61 -> 60
67 -> 33
71 -> 35
73 -> 8
79 -> 13
83 -> 41
89 -> 44
97 -> 96
101 -> 4
103 -> 34
107 -> 53
109 -> 108
113 -> 112
127 -> 42
131 -> 130
137 -> 8
139 -> 46
149 -> 148
151 -> 75
157 -> 78
163 -> 81
167 -> 166
173 -> 43
179 -> 178
181 -> 180
191 -> 95
193 -> 192
197 -> 98
199 -> 99
回复 原文
南渊 2025-02-16 03:19:24

谢谢Andrey Tyukin。

要记住的简单术语：

  1. x％y = z，然后再次（x％y）％y = z

  2. （x + y）％z ==（x％z + y％z）％z
    请记住这一点。

因此，您一次将任何数字分解为一些R数字。 IE断开3456733当r = 6中的3 * 10功率（6 * 1） + 446733 * 10功率（6 * 0）。

您可以将12536382626373分解为12 * 10功率（6 * 2）。 + 536382 * 10功率（6 * 1） + 626373 * 10功率（6 * 0）

观察到这里的r为6

。我们说，我们将模量应用于上述分解的系数。

那么系数总和如何代表整数的总和？

当上述分解中的“ 10个功率（6* noting）” Modulo变成1时，该特定术语的模型将等于系数的Modulo。这意味着10个功率（r*任何东西）无效。您可以通过使用公式1＆amp; 2检查为什么它不会产生效果。

其他类似的术语10功率（r * nothing）也将使Modulo为1。即，如果您可以证明（10 power r）modulo是1。然后（10 power r * nothing）也是1。

但是重要的是是我们应该具有等于1的10功率（r）。然后，每10个功率（r * nothing）是1，导致数字的模量等于r数字之和划分的模量。

结论：在（10个功率r）中找到R，使给定的质量数将留下1个提醒。

这也意味着最小的9….. 9可以排除在给定的质量数字r中。

Thank you andrey tyukin.

Simple terms to remember:

  1. When x%y =z then (x%y)%y again =z

  2. (X+y)%z == (x%z + y%z)%z
    keep this in mind.

So you break any number into some r digits at a time together. I.e. break 3456733 when r=6 into 3 * 10 power(6 * 1) + 446733 * 10 power(6 * 0).

And you can break 12536382626373 into 12 * 10 power (6 * 2). + 536382 * 10 power (6 * 1) + 626373 * 10 power (6 * 0)

Observe that here r is 6.

So when we say we combine the r digits and sum them together and apply modulo. We are saying we apply modulo to coefficients of above breakdown.

So how come coefficients sum represents whole number’s sum?

When the “10 power (6* anything)” modulo in the above break down becomes 1 then that particular term’s modulo will be equal to the coefficient’s modulo. That means the 10 power (r* anything) is of no effect. You can check why it will have no effect by using the formulas 1&2.

And the other similar terms 10 power (r * anything) also will have modulo as 1. I.e. if you can prove that (10 power r)modulo is 1. Then (10 power r * anything) is also 1.

But the important thing is we should have 10 power (r) equal to 1. Then every 10 power (r * anything) is 1 that leads to modulo of number equal to sum of r digits divided modulo.

Conclusion: find r in (10 power r) such that the given prime number will leave 1 as reminder.

That also mean the smallest 9…..9 which is divisible by given prime number decides r.

回复 原文
~没有更多了~

关于作者

请持续率性

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

牛↙奶布丁

文章 0 评论 0

COSO

文章 0 评论 0

落叶

文章 0 评论 0

暗地喜欢

文章 0 评论 0

qq_i8qOEG

文章 0 评论 0

qq_Wl4Sbi

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文