結果

問題 No.800 四平方定理
ユーザー lam6er
提出日時 2025-03-20 21:14:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 292 ms / 2,000 ms
コード長 868 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,624 KB
実行使用メモリ 138,468 KB
最終ジャッジ日時 2025-03-20 21:14:59
合計ジャッジ時間 5,561 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input_line = sys.stdin.readline().strip()
    N, D = map(int, input_line.split())
    
    max_sum_xy = 2 * N * N
    sum_counts = [0] * (max_sum_xy + 1)
    
    # Precompute x squares
    x_sqs = [x * x for x in range(N + 1)]
    
    # Fill sum_counts with counts of x^2 + y^2
    for x in range(1, N + 1):
        x_sq = x_sqs[x]
        for y in range(1, N + 1):
            s = x_sq + y * y
            if s <= max_sum_xy:
                sum_counts[s] += 1
    
    # Precompute z squares
    z_sqs = [z * z for z in range(N + 1)]
    
    ans = 0
    for w in range(1, N + 1):
        t = w * w + D
        temp = 0
        for z in range(1, N + 1):
            a = t - z_sqs[z]
            if 2 <= a <= max_sum_xy:
                temp += sum_counts[a]
        ans += temp
    
    print(ans)

if __name__ == "__main__":
    main()
0