【每日一题20220928】好友数据对

:woman_mage: 一个数字的真除数是除了自身之外的所有整除数的集合。例如,对于100,它们是1、2、4、5、10、20、25和50。

设s(n)是n的这些真除数之和。将buddy称为两个正整数,这样每个数的真除数的和比另一个数多一个:(n,m)是一对伙伴,如果s(m)=n+1和s(n)=m+1

例如,48和75就是这样一对:

48的除数是:1、2、3、4、6、8、12、16、24–>和:76=75+1

75的除数是:1、3、5、15、25–>和:49=48+1

任务

给定两个正整数start和limit,函数buddy(start,limit)应该返回buddy对的第一对(n m),这样n(正整数)就在 start 和 limits 之间;m可以大于极限,并且必须大于n

如果没有满足条件的好友数据对,则返回 “Nothing”

示例

buddy(10,50)返回[48,75]

buddy(48,50)返回[48,75]

题目难度:一般
题目来源: Buddy Pairs II | Codewars

from typing import Union

def buddy(start: int, limit: int) -> Union[list, str]:
    # your code here
    return []

assert buddy(10, 50) == [48, 75]
assert buddy(2177, 4357) == "Nothing"
assert buddy(57345, 90061) == [62744, 75495]
assert buddy(1071625, 1103735) == [1081184, 1331967]
from typing import Union


def isdivisor(num):
    lresult = []
    for i in range(1, num // 2 + 1):
        if num % i == 0:
            lresult.append(i)
    return lresult


def buddy(start: int, limit: int) -> Union[list, str]:
    for i in range(start, limit):
        lresult1 = isdivisor(i)
        lsum = sum(lresult1) - 1
        lresult2 = isdivisor(lsum)
        if sum(lresult2) - 1 == i and i < lsum:
            return [i, lsum]
    return "Nothing"

def buddy(start: int, limit: int) -> Union[list, str]:
    import math
    def inner(n):
        # 求因子
        res = 1
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                if i != n // i:
                    res += i + n // i
                else:
                    res += i
        return res

    n = start
    while n<=limit:
        res= inner(n)
        if res-1<=n or inner(res-1)-1!=n:
            n+=1
        else:
            return [n,res-1]
    else:
        return "Nothing"
1 Like

呃…我这运算时间巨长

from typing import Union


def buddy(start: int, limit: int) -> Union[list, str]:
    i_list = []
    j_list = []
    for n in range(start, limit + 1):
        for i in range(1, n):
            if n % i == 0:
                i_list.append(i)
        sn = sum(i_list)
        i_list = []
        m = sn - 1
        if m <= n:
            continue
        for j in range(1, m):
            if m % j == 0:
                j_list.append(j)
        sm = sum(j_list)
        j_list = []
        if sm == n + 1:
            return [n, m]
        else:
            continue
    return "Nothing"


assert buddy(10, 50) == [48, 75]
assert buddy(2177, 4357) == "Nothing"
assert buddy(57345, 90061) == [62744, 75495]
assert buddy(1071625, 1103735) == [1081184, 1331967]

认真读了读,没看明白大佬的解法,能简单讲下思路吗?

我这也是第3条case开始需要运行很久…

def buddy(start: int, limit: int) -> Union[list, str]:
    def find_true_divisor(num):  # 返回真除数集合
        return [i for i in range(1, num) if num % i == 0]

    for n in range(start, limit + 1):
        m = sum(find_true_divisor(n)) - 1
        if m > n and sum(find_true_divisor(m)) - 1 == n:  # m 必须大于 n
            return [n, m]
    else:
        return "Nothing"
关闭