python - 寻找 "decent"数字算法推理？

Question

问题

夏洛克·福尔摩斯对他的大敌莫里亚蒂教授越来越偏执。他所有想要制服莫里亚蒂的努力都白费了。这些天夏洛克正在和华生医生一起解决一个问题。沃森提到，中央情报局最近在他们的 super 计算机“野兽”上遇到了奇怪的问题。

今天下午，夏洛克收到了莫里亚蒂的来信，说他给“野兽”感染了病毒。此外，纸币上印有数字N。经过一些计算，Sherlock 发现要清除病毒的关键是具有 N 位的最大“体面”数字。

一个“体面”的数字有-

• 3 或 5 或两者作为其数字。
• 不允许使用其他数字。
• 3 出现的次数可以被 5 整除。
• 5 出现的次数可以被 3 整除。

与此同时，破坏“野兽”的计数器运行得非常快。你能拯救“野兽”，并在夏洛克之前找到 key 吗？

输入格式第一行将包含一个整数 T，即测试用例的数量。接下来是 T 行，每行包含一个整数 N，即数字中的位数

输出格式具有 N 位数字的最大体面数字。如果不存在这样的数字，告诉 Sherlock 他错了并打印 '-1'

约束条件1<=T<=201<=N<=100000

示例输入

4
1
3
5
11

示例输出

-1
555
33333
55555533333

解释对于 N=1，没有这样的数字。

对于 N=3，555 是唯一可能的数字。

对于 N=5，33333 是唯一可能的数字。

对于N=11，55555533333和所有数字排列都是有效数字，其中给定的数字是最大的。

回答

for _ in range(int(input())):
    n = int(input())
    c = 5*(2*n%3)
    if c > n:
        print(-1)
    else:
        print('5' * (n-c) + '3'*c)

问题

有人能解释一下背后的原因吗？具体来说，“c”变量的赋值是做什么的？

来源:https://www.hackerrank.com/challenges/sherlock-and-the-beast

Answer 1

数学解决方案:

设 a = 5 的 len，b = 3 的 len。所以

a + b = N

我们知道3整除a，5整除b，所以设a = 3n, b = 5m

3n+5m = N

这是一个丢番图方程 (http://en.wikipedia.org/wiki/Diophantine_equation)，一个解为 (n0, m0) = (2N, -N)，通解为

(n,m) = (5k+2N, 3K-N), k 任意整数

现在的问题是最小化 3k-N 的数量(因为你想要更多的“5”)，这样 3k-N > 0。这与从 N 中找到 3k 是 3 的下一个倍数的 k 相同。

例如，如果 N = 10 或 11，我们正在寻找 3k = 12，或 k = 4。

3k-N 因此是 N 和下一个 3 的倍数之间的距离。解决方案的作者声称 3k-N = 2N%3 ，您通过穷尽证明了这一点，评估 N%3 = 的情况0、1 和 2。郑重声明，表达式“2N%3”中的“2”不是唯一的，它适用于序列 2、5、8、11... 中的任意数字，以及为什么作者选择了这个特殊的表达方式，我不能说。

你也可以想想这个意义上的N%3是如何接近N的下一个3的LOWER倍数。