算法:分解整数 X 以获得尽可能多的不同正整数 (Y1...Yk),以便 (Y1+1)(Y2+1)...(Yk+1) = X
Algorithm: Factorize a integer X to get as many distinct positive integers(Y1...Yk) as possible so that (Y1+1)(Y2+1)...(Yk+1) = X
最近在open.kattis.com遇到了一道算法题。
问题的 link 是 https://open.kattis.com/problems/listgame2。
基本上,这是一个问题,要求玩家分解整数 X (10^3 <= X <= 10^15) 以获得尽可能多的 distinct 个正整数 (Y1,...,Yk) 尽可能 (Y1+1)(Y2+1)⋯(Yk+1) = X.
我已经想出了一个使用 Python3 的解决方案,它确实通过了几个测试用例,但其中一个失败了:MyStatus
我的代码是:
def minFactor(n, start):
maxFactor = round(n**0.5)
for i in range(start, maxFactor+1):
if n % i == 0:
return i
return n
def distinctFactors(n):
curMaxFactor = 1
factors = []
while n > 1:
curMaxFactor = minFactor(n, curMaxFactor+1)
n //= curMaxFactor
factors.append(curMaxFactor)
# This is for the situation where the given number is the square of a prime number
# For example, when the input is 4, the returned factors would be [2,2] instead of [4]
# The if statement below are used to fix this flaw
# And since the question only requires the length of the result, deleting the last factor when repeat do works in my opinion
if factors[-1] in factors[:-1]:
del factors[-1]
return factors
num = int(input())
print(len(distinctFactors(num)))
具体来说,上面代码里面我的想法很简单。例如,当给定输入为 36 时,我 运行 minFactor 函数查找 36 的最小因子为 2(在这种情况下忽略 1)。然后,我通过执行 36/2 得到 18 并调用 minFactor(18,3) 因为 2 不再不同所以我开始找到 18 乘以 3 的最小因子。它显然是 3,所以我通过执行 18 得到 6 /3 在函数 distinctFactors 中调用 minFactor(6,4),因为 4 小于 sqrt(6) 或 6**0.5,所以 6 本身将被返回,我最终得到列表因子 [2,3,6],这是正确的。
我已经仔细检查了我的代码和算法几个小时,但我仍然无法弄清楚为什么我没有通过测试用例,有人可以帮助我解决我的困境吗???等待回复。
考虑数字 2**6.11**5
。
您的算法将找到 5 个因素:
2
2**2
2**3
11
11**2
(11**2 this will be discarded as it is a repeat)
长度为 6 的答案是:
2
2**2
11
11**2
2*11
2**2*11
最近在open.kattis.com遇到了一道算法题。 问题的 link 是 https://open.kattis.com/problems/listgame2。 基本上,这是一个问题,要求玩家分解整数 X (10^3 <= X <= 10^15) 以获得尽可能多的 distinct 个正整数 (Y1,...,Yk) 尽可能 (Y1+1)(Y2+1)⋯(Yk+1) = X.
我已经想出了一个使用 Python3 的解决方案,它确实通过了几个测试用例,但其中一个失败了:MyStatus
我的代码是:
def minFactor(n, start):
maxFactor = round(n**0.5)
for i in range(start, maxFactor+1):
if n % i == 0:
return i
return n
def distinctFactors(n):
curMaxFactor = 1
factors = []
while n > 1:
curMaxFactor = minFactor(n, curMaxFactor+1)
n //= curMaxFactor
factors.append(curMaxFactor)
# This is for the situation where the given number is the square of a prime number
# For example, when the input is 4, the returned factors would be [2,2] instead of [4]
# The if statement below are used to fix this flaw
# And since the question only requires the length of the result, deleting the last factor when repeat do works in my opinion
if factors[-1] in factors[:-1]:
del factors[-1]
return factors
num = int(input())
print(len(distinctFactors(num)))
具体来说,上面代码里面我的想法很简单。例如,当给定输入为 36 时,我 运行 minFactor 函数查找 36 的最小因子为 2(在这种情况下忽略 1)。然后,我通过执行 36/2 得到 18 并调用 minFactor(18,3) 因为 2 不再不同所以我开始找到 18 乘以 3 的最小因子。它显然是 3,所以我通过执行 18 得到 6 /3 在函数 distinctFactors 中调用 minFactor(6,4),因为 4 小于 sqrt(6) 或 6**0.5,所以 6 本身将被返回,我最终得到列表因子 [2,3,6],这是正确的。
我已经仔细检查了我的代码和算法几个小时,但我仍然无法弄清楚为什么我没有通过测试用例,有人可以帮助我解决我的困境吗???等待回复。
考虑数字 2**6.11**5
。
您的算法将找到 5 个因素:
2
2**2
2**3
11
11**2
(11**2 this will be discarded as it is a repeat)
长度为 6 的答案是:
2
2**2
11
11**2
2*11
2**2*11