平衡离心机配置

Question

给定离心机大小的输入N，我需要找出平衡配置的数量。完整的描述是这里。

离心机是一种将多个试管高速旋转的设备。它由一个圆柱形转子组成，圆柱形转子的孔沿转子周长均匀分布。由于该装置在高速运行，所有管的质量中心必须与转子中心重合。我们假设所有的管子都有相同的质量。为了简单起见，我们还假定管子是点质量，固定在转子上。离中心的距离都是一样的。你可以安全地假设管子的(x,y)坐标是R\sin a, R\cos a，而a = 2\pi\frac{k}{n}的问题是:给定一个有N个孔和K管的离心机，它能平衡它吗？例1:给定N=6，K的可能值为2,3,4,6。例2:给定N= 12，可以平衡5根管:将3根均匀分散(每4孔)，然后找到一对对空孔，然后插入剩下的2根管。例3:给定N= 10，就不可能平衡7根管子:放置5根均匀分散的管子，并且没有相反的空孔！输入第1行:离心机容量的整数N。输出第1行:不同可能值K的个数的整数M。

这是我的密码：

import numpy as np

N=int(input())
angle = 2*np.pi/N
z = complex(np.cos(angle), np.sin(angle))


import itertools
combs = []
lst = range(1,N)
for i in range(2, N-1):
    combs.append(i)
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.append(els)


count=1
lis = []
while count<=len(combs):
    for a in range(len(combs[count])):
        s=0
        for b in range(len(combs[count][a])):
            s+=z**combs[count][a][b]
        if abs(s)<1e-10:
            lis.append(combs[count][a])
    count+=2


lengths = []
for i in lis:
    if len(i) not in lengths:
        lengths.append(len(i))

print(len(lengths)+1)

代码运行良好，但在输入大小超过20之后会减慢，并且由于for循环，当输入增加到50或更高时，实际上无法使用。我该如何优化它？

Answer 1

这不是一个评论，而是一个延伸的评论。

代码无法进行有意义的优化。不过，没几个音符。

• 第一，你不可强暴。这几乎不可避免地是错误的。
• 接下来，你必须意识到这是一个数论问题.甚至测试用例的名称也表明了这一点。除其他外，这意味着用1e-10测试和是不对的。
• 最后，请看问题中引用的视频。这是一个巨大的破坏者，它没有提供一个索赔的证据。这个证明远非微不足道；如果您对这个证据感兴趣，那么这是一个非常有趣的读物(触发警告:繁重的数学)。

Answer 2

有两个主要问题：

1. 枚举所有组合，即使是那些明显不平衡的组合。
2. 浮点演算在组合问题中的应用

仔细阅读这个任务，特别是示例2和3，这两个例子暗示了一个更好的算法：

1. 分解N。N=12的因子是[2,3]，它告诉我们所有的管都是平衡对或三重态的成员。
2. 查找与K相加的所有因素组合。对于N=12, K=10，有两种解决方案：2+2+2+2+2=10和2+2+3+3=10。
3. 找出解决方案是否有效。对于N=10, K=7，唯一的解决方案是2+5=7，它是无效的(参见示例3)。

对于较大的K值，平衡孔而不是管。所以N=12, K=10和N=12, K=2是一样的。

Answer 3

在问了这个问题整整一年之后，以下是一个基于动态规划的解决方案，这要感谢最初帖子中的评论Niako (在问题中链接)：

N = int(input())

def primeFactorization(n):
    """ Return the prime factors of n """
    p_factors = []
    lastresult = n
    while 1:
        if lastresult == 1:
            break
        c = 2
        while 1:
            if lastresult % c == 0:
                break
            c += 1
        if c not in p_factors:
            p_factors.append(c)
        lastresult /= c
    return p_factors

F = primeFactorization(N)
R = [False]*(N+1)
R[0] = True
for p in F:
    for n in range(p,N+1):
        R[n] = R[n] or R[n-p]

sols = []
for i in range(2,int(N/2)+1):
    if R[i]==True:
        sols.append(i)
        sols.append(N-i)
sols.append(N)
print(len(set(sols)))

这是可行的，除了两个测试用例，即用例7和8(即输入33和35，预期输出分别为13和11，但该程序为两者输出15 )。如果有人能指出原因，那就太好了。