一道数学题，请问这个题还有更有的解法吗？
本帖最后由 zhangjinxuan 于 2023-5-23 18:07 编辑这道题：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 18:40 编辑
可以使用预处理出质数使效率提升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 =
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 and n != 1: return 2
while n % primes == 0:
# print(n)
yinshu] = yinshu.get(primes, 0) + 1
n = n // primes
i += 1
except:
yinshu = 1
s = 1
for i in yinshu:
s *= (yinshu+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 = '')
页:
[1]