結果

問題 No.800 四平方定理
コンテスト
ユーザー Ueki
提出日時 2019-03-17 23:19:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,356 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 259,500 KB
最終ジャッジ日時 2024-07-08 02:42:00
合計ジャッジ時間 22,369 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1 RE * 1
other AC * 1 WA * 24 RE * 3 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import sqrt
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, D = map(int, input().split())


L = [v**2 for v in range(1, N+1)]
LIM = N**2+D


def fact(n):
    if n == 3:
        return 6
    elif n == 2:
        return 3
    else:
        return 1


def solve2():
    left = [x+y for x in L for y in L]
    left = sorted(left)
    ans = 0
    for w in L:
        for z in L:
            tmp = w-z+D
            ind = bisect.bisect_left(left, tmp)
            if left[ind] == tmp:
                rt = sqrt(tmp/2)
                if rt == int(rt):
                    ans += 1
                else:
                    ans += 2
    print(ans)


def solve1():
    ans = 0
    for x in range(1, N+1):
        tmp1 = x**2
        if tmp1 > LIM:
            break
        for y in range(x, N+1):
            tmp2 = tmp1+y**2
            if tmp2 > LIM:
                break
            for z in range(y, N+1):
                tmp3 = tmp2 + z**2
                if tmp3 > LIM:
                    break
                r = tmp3-D
                if r <= 0:
                    continue
                else:
                    rt = sqrt(r)
                    if rt <= N and rt == int(rt):
                        ans += fact(len(set([x, y, z])))
    print(ans)


# solve1()
solve2()
0