[已解决]一道数学题，请问这个题还有更有的解法吗？

zhangjinxuan

这道题：https://fishc.com.cn/forum.php?mod=viewthread&tid=223880

我的时间复杂度达到了 O(t sqrt(n))， 我不是特别满意，就想问一下这道题还有更好的解法吗？

本人数学不好，大佬勿喷……

给定 t 个正整数字 n， 请问对于每个 n， a^2 + n = b^2 一共有多少非负整数解（含0）？

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-30 16:39:23

可以使用预处理出质数使效率提升

def prime():
    global primes
    def is_prime(n):
        if n<2: return False
        return all(n%i for i in range(2, int(n**0.5+1)))
    primes = [i for i in range(int(1e9**0.5+2)) if is_prime(i)]
def count(yinshu, exp_2):
    # print(yinshu, exp_2)
    if exp_2 == 0: return yinshu // 2 + yinshu % 2
    if exp_2 == 1: return 0
    s = (yinshu // 2) * (exp_2-1)
    s += (yinshu % 2) * (exp_2 // 2)
    return s

def count_yinshu(n):
    #print(n, end = ' ')
    i = 1
    yinshu = dict()
    try:
        while n != 1:
            if n < primes[i] and n != 1: return 2
            while n % primes[i] == 0:
                # print(n)
                yinshu[primes[i]] = yinshu.get(primes[i], 0) + 1
                n = n // primes[i]
            i += 1
    except:
        yinshu[n] = 1
    s = 1
    for i in yinshu:
        s *= (yinshu[i]+1)
    return s

def count_2_exp(n):
    exp_2 = 0
    while not n % 2:
        n //= 2
        exp_2 += 1
    return exp_2, n

def count_n(n):
    exp_2, new_n = count_2_exp(n)
    return count(count_yinshu(new_n), exp_2)

input()
n = list(map(int, input().split()))
#import time
#start = time.time()
prime()
for i in n:
    print(count_n(i), end = ' ')
#end = time.time()
#print('\n', end - start, sep = '')

跳转到最佳答案楼层

tommyyu

可以使用预处理出质数使效率提升

def prime():
    global primes
    def is_prime(n):
        if n<2: return False
        return all(n%i for i in range(2, int(n**0.5+1)))
    primes = [i for i in range(int(1e9**0.5+2)) if is_prime(i)]
def count(yinshu, exp_2):
    # print(yinshu, exp_2)
    if exp_2 == 0: return yinshu // 2 + yinshu % 2
    if exp_2 == 1: return 0
    s = (yinshu // 2) * (exp_2-1)
    s += (yinshu % 2) * (exp_2 // 2)
    return s

def count_yinshu(n):
    #print(n, end = ' ')
    i = 1
    yinshu = dict()
    try:
        while n != 1:
            if n < primes[i] and n != 1: return 2
            while n % primes[i] == 0:
                # print(n)
                yinshu[primes[i]] = yinshu.get(primes[i], 0) + 1
                n = n // primes[i]
            i += 1
    except:
        yinshu[n] = 1
    s = 1
    for i in yinshu:
        s *= (yinshu[i]+1)
    return s

def count_2_exp(n):
    exp_2 = 0
    while not n % 2:
        n //= 2
        exp_2 += 1
    return exp_2, n

def count_n(n):
    exp_2, new_n = count_2_exp(n)
    return count(count_yinshu(new_n), exp_2)

input()
n = list(map(int, input().split()))
#import time
#start = time.time()
prime()
for i in n:
    print(count_n(i), end = ' ')
#end = time.time()
#print('\n', end - start, sep = '')