105學年度台中區資訊能力競賽程式題Q3(2^k的4個自然數表示法)

Lagrange's four-square theorem：每個正整數均可表示為4個整數的平方和
 ==>  m^2=a^2+b^2+c^2+d^2
(大陸第七屆藍橋杯試題)

Python code：

import time
m=int(input()) #輸入一正整數，找出所有的四平方和表示法
aa=int(m**0.5)+1
flag=0
start=time.clock()
for a in range(0,aa):
    bb=int((m-a*a)**0.5)+1
    for b in range(a,bb):
        cc=int((m-a*a-b*b)**0.5)+1
        for c in range(b,cc):
            d=int((m-a*a-b*b-c*c)**0.5)
            if a*a+b*b+c*c+d*d==m :   
                 flag+=1
                 if flag==1:
                    print(a,b,c,d)
                    end=time.clock()
                    print('It costs time',end-start,'seconds')


@ 正整數化四平方和的解數不一定只有唯一解
     如10=0^2+0^2+1^2+3^2
            =1^2+1^2+2^2+2^2

😺 以下的程式碼是可以找出由小到大排列的a、b、c、d的所有組數：

@藍橋杯規定只需找出一組解就好但執行時間不得超過3秒，
    所以必須優化，原本必須要4個for-loop，但最後一個迴圈
    可省略，讓d=m-a^2-b^2-c^2就好，本人測試過773535，
    如果是4個迴圈，需時22秒，但改成3個，時間縮短成0.36
    秒，大大提升效率。