結果
| 問題 | No.800 四平方定理 |
| ユーザー |
 Keroru
|
| 提出日時 | 2020-05-01 03:09:16 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,506 bytes |
| コンパイル時間 | 161 ms |
| コンパイル使用メモリ | 82,344 KB |
| 実行使用メモリ | 286,344 KB |
| 最終ジャッジ日時 | 2024-06-01 09:43:43 |
| 合計ジャッジ時間 | 23,232 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 103 ms
88,048 KB |
| testcase_01 | AC | 109 ms
85,484 KB |
| testcase_02 | AC | 104 ms
82,504 KB |
| testcase_03 | AC | 103 ms
83,488 KB |
| testcase_04 | AC | 101 ms
82,116 KB |
| testcase_05 | AC | 104 ms
83,212 KB |
| testcase_06 | AC | 114 ms
88,432 KB |
| testcase_07 | AC | 105 ms
83,900 KB |
| testcase_08 | AC | 113 ms
88,228 KB |
| testcase_09 | AC | 112 ms
86,228 KB |
| testcase_10 | AC | 1,410 ms
264,452 KB |
| testcase_11 | AC | 1,661 ms
263,956 KB |
| testcase_12 | AC | 1,597 ms
264,188 KB |
| testcase_13 | AC | 1,446 ms
264,692 KB |
| testcase_14 | AC | 1,637 ms
263,016 KB |
| testcase_15 | AC | 1,624 ms
263,164 KB |
| testcase_16 | AC | 1,669 ms
262,780 KB |
| testcase_17 | AC | 1,699 ms
263,160 KB |
| testcase_18 | AC | 1,673 ms
262,812 KB |
| testcase_19 | AC | 1,669 ms
262,880 KB |
| testcase_20 | AC | 68 ms
70,600 KB |
| testcase_21 | AC | 67 ms
69,708 KB |
| testcase_22 | AC | 1,701 ms
263,620 KB |
| testcase_23 | TLE | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
ソースコード
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
org_inp=[];g=[[] for i in range(V)]
FromStdin=True if ls==None else False
for i in range(E):
if FromStdin:
inp=LI()
a,b,c=(inp+[1])[:3]
org_inp.append(inp)
else:
index=0
a,b,c=(ls[i]+[1])[:3]
if index==1:a-=1;b-=1
aa=(a,c);bb=(b,c);g[a].append(bb)
if not Directed:g[b].append(aa)
return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
mp=[boundary]*(w+2);found={}
for i in range(h):
s=input()
for char in search:
if char in s:
found[char]=((i+1)*(w+2)+s.index(char)+1)
mp_def[char]=mp_def[replacement_of_found]
mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
mp+=[boundary]*(w+2)
return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
rt=[]
for tb in range(n**k):
s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
return rt
def show(*inp,end='\n'):
if show_flg:print(*inp,end=end)
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
class Comb:
def __init__(self,n,mo=10**9+7):
self.fac=[0]*(n+1)
self.inv=[1]*(n+1)
self.fac[0]=1
self.fact(n)
for i in range(1,n+1):
self.fac[i]=i*self.fac[i-1]%mo
self.inv[n]*=i
self.inv[n]%=mo
self.inv[n]=pow(self.inv[n],mo-2,mo)
for i in range(1,n):
self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
return
def fact(self,n):
return self.fac[n]
def invf(self,n):
return self.inv[n]
def comb(self,x,y):
if y<0 or y>x:
return 0
return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
show_flg=False
show_flg=True
## Segment Tree ##
## Initializer Template ##
# Range Sum: sg=SegTree(n)
# Range Minimum: sg=SegTree(n,inf,min,inf)
class SegTree:
def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
self.n=n
self.ide_ele=ide_ele=ide
self.num=num=2**(n-1).bit_length()
self.seg=seg=[self.ide_ele]*2*self.num
self.lazy=lazy=[self.ide_ele]*2*self.num
self.segfun=segfun=function
#set_val
if init_ls==None:
for i in range(n):
self.seg[i+self.num-1]=init_val
else:
for i in range(n):
self.seg[i+self.num-1]=init_ls[i]
#build
for i in range(self.num-2,-1,-1):
self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
def update(self,k,x):
k += self.num-1
self.seg[k] = x
while k:
k = (k-1)//2
self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
def evaluate(k,l,r): #遅延評価処理
if lazy[k]!=0:
node[k]+=lazy[k]
if(r-l>1):
lazy[2*k+1]+=lazy[k]//2
lazy[2*k+2]+=lazy[k]//2
lazy[k]=0
def query(self,p,q):
if q<=p:
return self.ide_ele
p += self.num-1
q += self.num-2
res=self.ide_ele
while q-p>1:
if p&1 == 0:
res = self.segfun(res,self.seg[p])
if q&1 == 1:
res = self.segfun(res,self.seg[q])
q -= 1
p = p//2
q = (q-1)//2
if p == q:
res = self.segfun(res,self.seg[p])
else:
res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
return res
def find_min_index(self,p,q,m):
if q<=p:
return self.ide_ele
p += self.num-1
q += self.num-2
res=self.ide_ele
while q-p>1:
if p&1 == 0:
res = self.segfun(res,self.seg[p])
if q&1 == 1:
res = self.segfun(res,self.seg[q])
q -= 1
p >>= 1
q = (q-1)//2
if p == q:
res = self.segfun(res,self.seg[p])
else:
res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
return res
def __str__(self):
# 生配列を表示
rt=self.seg[self.num-1:self.num-1+self.n]
return str(rt)
class Tree:
def __init__(self,inp_size=None,init=True):
if init:
self.stdin(inp_size)
return
def stdin(self,inp_size=None):
if inp_size==None:
self.size=int(input())
else:
self.size=inp_size
self.edges,_=GI(self.size,self.size-1)
return
def listin(self,ls):
self.size=len(ls)+1
self.edges,_=GI(self.size,self.size-1,ls)
return
def __str__(self):
return str(self.edges)
def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
q=deque()
q.append(x)
v=[-1]*self.size
v[x]=root_v
while q:
c=q.pop()
for nb,d in self.edges[c]:
if v[nb]==-1:
q.append(nb)
v[nb]=func(v[c],nb,d)
return v
def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
q=deque()
q.append((-1,x))
v=[None]*self.size
v[x]=root_v
et=[]
while q:
cb,ce=q.pop()
et.append(ce)
for nb,d in self.edges[ce]:
if v[nb]==None:
q.append((nb,ce))
q.append((ce,nb))
v[nb]=func(v[ce],nb,d)
vid=[[-1,-1]for i in range(self.size)]
for i,j in enumerate(et):
if vid[j][0]==-1:
vid[j][0]=i
else:
vid[j][1]=i
return v,et,vid
def LCA_init(self,depth,et):
self.st=SegTree(self.size*2-1,func=min,ide=inf)
for i,j in enumerate(et):
self.st.update(i,j)
self.LCA_init_stat==True
return
def LCA(self,root,x,y):
if self.LCA_init_stat==False:
depth,et,vid=self.EulerTour(root)
self.LCA_init(depth,et)
return self.st.query(x,y+1)
n,d=LI()
m=defaultdict(int)
t=defaultdict(int)
m={}
t={}
for x in range(1,n+1):
for y in range(1,n+1):
X=x*x
Y=y*y
if X+Y in m:
m[X+Y]+=1
else:
m[X+Y]=1
if X-Y+d in t:
t[X-Y+d]+=1
else:
t[X-Y+d]=1
ans=0
for i in m:
if i in t:
ans+=m[i]*t[i]
print(ans)