01/10/2018, 09:38
Giúp mình tối ưu thuật toán Challenge sumSquares
Đề : Cho số nguyên dương k, hỏi có bao nhiêu cách biểu diễn k dưới dạng tổng của không quá 2 số chính phương, k = a^2 + b^2 hoặc k = c^2 . Vd k = 25
25 = 52;
25 = 32 + 42;
25 = 42 + 32.
=> số cách bằng 3
Mình nghe theo một comment là brute force có thể qua được nên đã cố thử … kết quả là LTE test cuối. Ý tưởng là lấy j = k - i*i rồi xem j có phải số chính phương không nhưng mà do dùng nhiều phép nhân với lấy căn nên bị chậm. Ai giúp mình cải tiến nó lên hay cho gợi ý với @.@ cảm ơn nhiều. https://codefights.com/challenge/mphk8gHzaN5KQAJij
from math import sqrt
def sumSquares(k):
if k == 0 or k == 1:
return 1
while k%2==0:
k//=2
c = 0
sqrtk = int(sqrt(k))
for i in range(sqrtk+1):
j = k - i*i
if is_square(j):
c+=1
if sqrtk*sqrtk == k:
return c - 1
return c
def is_square(i):
root = int(sqrt(i))
return root*root == i
Bài liên quan
đọc lại cái đề xem k==0 thì kết quả là bao nhiêu…
_ chơi gài thế mết chết, không đọc kĩ cái đề cứ cho 0! Thanks