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

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

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

1. def prime():
   
2.     global primes
   
3.     def is_prime(n):
   
4.         if n<2: return False
   
5.         return all(n%i for i in range(2, int(n**0.5+1)))
   
6.     primes = [i for i in range(int(1e9**0.5+2)) if is_prime(i)]
   
7. def count(yinshu, exp_2):
   
8.     # print(yinshu, exp_2)
   
9.     if exp_2 == 0: return yinshu // 2 + yinshu % 2
   
10.     if exp_2 == 1: return 0
    
11.     s = (yinshu // 2) * (exp_2-1)
    
12.     s += (yinshu % 2) * (exp_2 // 2)
    
13.     return s
    
14. 
    
15. def count_yinshu(n):
    
16.     #print(n, end = ' ')
    
17.     i = 1
    
18.     yinshu = dict()
    
19.     try:
    
20.         while n != 1:
    
21.             if n < primes[i] and n != 1: return 2
    
22.             while n % primes[i] == 0:
    
23.                 # print(n)
    
24.                 yinshu[primes[i]] = yinshu.get(primes[i], 0) + 1
    
25.                 n = n // primes[i]
    
26.             i += 1
    
27.     except:
    
28.         yinshu[n] = 1
    
29.     s = 1
    
30.     for i in yinshu:
    
31.         s *= (yinshu[i]+1)
    
32.     return s
    
33. 
    
34. def count_2_exp(n):
    
35.     exp_2 = 0
    
36.     while not n % 2:
    
37.         n //= 2
    
38.         exp_2 += 1
    
39.     return exp_2, n
    
40. 
    
41. def count_n(n):
    
42.     exp_2, new_n = count_2_exp(n)
    
43.     return count(count_yinshu(new_n), exp_2)
    
44. 
    
45. input()
    
46. n = list(map(int, input().split()))
    
47. #import time
    
48. #start = time.time()
    
49. prime()
    
50. for i in n:
    
51.     print(count_n(i), end = ' ')
    
52. #end = time.time()
    
53. #print('\n', end - start, sep = '')
    

复制代码

跳转到最佳答案楼层

tommyyu

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

1. def prime():
   
2.     global primes
   
3.     def is_prime(n):
   
4.         if n<2: return False
   
5.         return all(n%i for i in range(2, int(n**0.5+1)))
   
6.     primes = [i for i in range(int(1e9**0.5+2)) if is_prime(i)]
   
7. def count(yinshu, exp_2):
   
8.     # print(yinshu, exp_2)
   
9.     if exp_2 == 0: return yinshu // 2 + yinshu % 2
   
10.     if exp_2 == 1: return 0
    
11.     s = (yinshu // 2) * (exp_2-1)
    
12.     s += (yinshu % 2) * (exp_2 // 2)
    
13.     return s
    
14. 
    
15. def count_yinshu(n):
    
16.     #print(n, end = ' ')
    
17.     i = 1
    
18.     yinshu = dict()
    
19.     try:
    
20.         while n != 1:
    
21.             if n < primes[i] and n != 1: return 2
    
22.             while n % primes[i] == 0:
    
23.                 # print(n)
    
24.                 yinshu[primes[i]] = yinshu.get(primes[i], 0) + 1
    
25.                 n = n // primes[i]
    
26.             i += 1
    
27.     except:
    
28.         yinshu[n] = 1
    
29.     s = 1
    
30.     for i in yinshu:
    
31.         s *= (yinshu[i]+1)
    
32.     return s
    
33. 
    
34. def count_2_exp(n):
    
35.     exp_2 = 0
    
36.     while not n % 2:
    
37.         n //= 2
    
38.         exp_2 += 1
    
39.     return exp_2, n
    
40. 
    
41. def count_n(n):
    
42.     exp_2, new_n = count_2_exp(n)
    
43.     return count(count_yinshu(new_n), exp_2)
    
44. 
    
45. input()
    
46. n = list(map(int, input().split()))
    
47. #import time
    
48. #start = time.time()
    
49. prime()
    
50. for i in n:
    
51.     print(count_n(i), end = ' ')
    
52. #end = time.time()
    
53. #print('\n', end - start, sep = '')
    

复制代码