算法:分解整数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中遇到了算法问题.该问题的链接为 https://open.kattis.com/problems/listgame2 .基本上，这是一个问题，要求玩家分解整数X(10 ^ 3< = X< = 10 ^ 15)，以获得尽可能多的 distinct 正整数(Y ₁ ，...，Y _k )尽可能使(Y ₁ +1)(Y ₂ +1)⋯(Y _k +1)= X.

I recently met a algorithm question in open.kattis.com. The question's link is https://open.kattis.com/problems/listgame2. Basically, it is a question ask the players to factorize a integer X (10^3 <= X <= 10^15) to get as many distinct positive integers (Y₁,...,Y_k) as possible such that (Y₁+1)(Y₂+1)⋯(Y_k+1) = X.

我已经想出了使用Python3的解决方案，该解决方案确实通过了多个测试用例，但其中一个失败了:

I already came up with a solution using Python3, which does pass several test cases but failed one of them: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不再是唯一的，所以我开始用3查找最小因子18.显然它是3，所以我通过执行18来得到6/3在distinctFactors函数中并调用minFactor(6,4)，因为4小于sqrt(6)或6 ** 0.5，所以将返回6本身，最后得到列表因子[2,3,6]，这是正确的.

Specifically, my idea inside the above code is quite simple. For example, when the given input is 36, I run the minFactor function to find that the minimum factor of 36 is 2 (1 is ignored in this case). Then, I get 18 by doing 36/2 and invoke minFactor(18,3) since 2 is no more distinct so I start to find the minimum factor of 18 by 3. And it is 3 clearly, so I get 6 by doing 18/3 in function distinctFactors and invoke minFactor(6,4), since 4 is smaller than sqrt(6) or 6**0.5 so 6 itself will be returned and I finally get the list factors as [2,3,6], which is correct.

我已经检查了几个小时的代码和算法，但是我仍然无法弄清楚为什么我无法通过测试用例，任何人都可以帮助我解决我的困境吗???等待回复.

I have scrutinised my code and algorithm for hours but I still cannot figure out why I failed the test case, could anyone help me with my dilemma??? Waiting for reply.

推荐答案

考虑数字 2 ** 6.11 ** 5 .

您的算法将找到5个因素:

Your algorithm will find 5 factors:

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

这篇关于算法:分解整数X以获得尽可能多的不同正整数(Y1 ... Yk)，以便(Y1 + 1)(Y2 + 1)...(Yk + 1)= X的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！