#39553: python 使用平方和公式
henry0985524680@gmail.com
(張弘勳)
學校
:
臺北市立建國高級中學
編號 : 192343
來源 : [39.12.34.245]
最後登入時間 ：
2024-10-31 20:28:41
a059. 完全平方和
| From: [111.243.102.250] |
發表日期
:
2024-03-06 02:37
平方和公式:1到n的平方和等於n(n+1)(2n+1)
假設給的兩數a,b
a以下的所有平方數=A
b以下的所有平方數=B
B必定涵蓋A，在a不是完全平方數的情況下，我們只需要使用SB-SA即是答案。
但如果a是完全平方數，像是a=4,b=25,A=1,4,B=1,4,9,16,25
這時計算S(B-A)=S(16,25)就會漏掉a本身
所以 if (a是完全平方數): a=a-1 就解決了問題
當然，在a=1時，我們在事實上讓a=0，然後去找到0的所有完全平方數和，這在數學的定義上是有問題的，
但我們使用的平方和公式不會受到影響，所以沒關係。
def Solution(a,b):
if a**(1/2)%1==0:
a-=1
while True:
if a**(1/2)%1==0:
break
else:
a-=1
while True:
if b**(1/2)%1==0:
break
else:
b-=1
a=a**(1/2)
b=b**(1/2)
a=(a*(a+1)*(2*a+1))/6
b=(b*(b+1)*(2*b+1))/6
return int(b-a)
n=int(input())
for i in range(1,n+1):
a=int(input())
b=int(input())
print(f'Case {i}: {Solution(a,b)}')
ZeroJudge Forum