結果

問題 No.2400 Product of Gaussian Integer
ユーザー kusirakusirakusirakusira
提出日時 2023-08-04 21:44:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 19,931 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 91,648 KB
最終ジャッジ日時 2024-10-14 19:42:01
合計ジャッジ時間 3,936 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 172 ms
91,392 KB
testcase_01 AC 166 ms
91,136 KB
testcase_02 AC 166 ms
91,392 KB
testcase_03 AC 167 ms
91,264 KB
testcase_04 AC 164 ms
91,136 KB
testcase_05 AC 165 ms
91,648 KB
testcase_06 AC 169 ms
91,392 KB
testcase_07 AC 164 ms
91,520 KB
testcase_08 AC 166 ms
91,392 KB
testcase_09 AC 166 ms
91,264 KB
testcase_10 AC 167 ms
91,136 KB
testcase_11 AC 168 ms
91,264 KB
testcase_12 AC 167 ms
91,520 KB
testcase_13 AC 168 ms
91,520 KB
testcase_14 AC 163 ms
91,392 KB
testcase_15 AC 165 ms
91,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# Python3/Pypy3
#-------------------------------------------------------------------
from bisect import *
import heapq
import collections
from collections import deque
from queue import Queue
from itertools import groupby
import itertools
import math
import array
import string
import copy
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from functools import reduce
from operator import and_, or_, xor
#------------------------------------------------------------------
INF = 10**20
mod = 998244353
MOD = 10**9+7
def YesNo(b): print("Yes") if b else print("No")
def YESNO(b): print("YES") if b else print("NO")
#---------------------------------------------------------------------
import sys
sys.setrecursionlimit(10 ** 5 + 10000)
input = sys.stdin.readline ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LIS(): return list(map(int, SI()))
def LA(f): return list(map(f, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return input().strip('\n')
def MS(): return input().split()
def LS(): return list(input().strip('\n'))
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def LMS(rows_number): return [MS() for _ in range(rows_number)]
#------------------------------------------------------------------------
######
def ceil(a,b): #
return (a+b-1)//b
def div(a,b,p): #mod pa/b(bp)
return (a*pow(b,p-2,p))%p
def transpose(A): #
A_t = []
for i in range(len(A[0])) :
tmp = []
for v in A :
tmp.append(v[i])
A_t.append(tmp)
return A_t
def removeDuplicates_2D(A): #
return list(map(list, set(map(tuple, A))))
def cumulativeSum_1D(A): #A
return list(itertools.accumulate(A))
def cumulativeSum_2D(S): #S =>
h = len(S)
w = len(S[0])
CS = [[0 for _ in range(w)]for _ in range(h)]
CCS = [[0 for _ in range(w)]for _ in range(h)]
for i in range(h):
for j in range(w):
if(j==0):
CS[i][0] = S[i][0]
else:
CS[i][j] = CS[i][j-1] + S[i][j]
for i in range(h):
for j in range(w):
if(i==0):
CCS[0][j] = CS[0][j]
else:
CCS[i][j] = CCS[i-1][j] + CS[i][j]
return CCS
def string_to_runLength(S: str): #/
grouped = groupby(S)
res = []
for k, v in grouped:
res.append((k, int(len(list(v)))))
return res
def runLength_to_string(L: "list[tuple]"): # =>
res = ""
for c, n in L:
res += c * int(n)
return res
def bfs(i,G,m = mod): # i: m:mod(998244353) => dist,pre,dp
n = len(G)
dist = [-1] * n
dp = [0] * n
pre = [-1] * n
que = deque()
dp[i] = 1
dist[i] = 0
que.append(i)
while que:
v = que.popleft()
for next_v in G[v]:
if dist[next_v] != -1:
if(dist[next_v]==dist[v]+1):
dp[next_v] += dp[v]
dp[next_v] %= m
continue
dist[next_v] = dist[v] + 1
dp[next_v] += dp[v]
dp[next_v] %= m
pre[next_v] = v
que.append(next_v)
return dist,pre,dp
def dijkstra(s,G): #s: => cost,pre | G:(,)
n = len(G)
hq = [(0, s)]
heapq.heapify(hq)
cost = [INF]*n
cost[s]= 0
pre = [-1] * n
while hq:
c,v = heapq.heappop(hq)
if c > cost[v]:
continue
for d,u in G[v]:
tmp = d+cost[v]
if tmp < cost[u]:
cost[u] = tmp
pre[u] = v
heapq.heappush(hq,(tmp,u))
return cost, pre
def coordinates(A): # ( : ),2(: ),
B = sorted(set(A))
C = { v: i for i, v in enumerate(B) }
D = { i: v for i, v in enumerate(B) }
E = list(map(lambda v: C[v], A))
return C, D, E
def eng_L(): return list(string.ascii_lowercase)
def ENG_L(): return list(string.ascii_uppercase)
def bit_len(n): #bit
return n.bit_length()
def bit_cnt(n): # bit1
cnt = 0
for i in range(bit_len(n)+1):
cnt += n>>i & 1
return cnt
def idx_le(A, x): # x / "No"
return bisect_right(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"
def idx_lt(A, x): # x / "No"
return bisect_left(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"
def idx_ge(A, x): # x / "No"
return bisect_left(A, x) if bisect_left(A, x) != len(A) else "No"
def idx_gt(A, x): # x / "No"
return bisect_right(A, x) if bisect_right(A, x) != len(A) else "No"
def cnt_le(A, x): # x
if(idx_le(A, x) == "No"): return 0
return idx_le(A, x) + 1
def cnt_lt(A, x): # x
if(idx_lt(A, x) == "No"): return 0
return idx_lt(A, x) + 1
def cnt_ge(A, x): # x
return len(A) - cnt_lt(A, x)
def cnt_gt(A, x): # x
return len(A) - cnt_le(A, x)
###/###
def allAnd(A): # AAND
return reduce(and_, A)
def allOr(A): # AOR
return reduce(or_, A)
def allXor(A): # AXOR
return reduce(xor, A)
def MEX(A): #AMEX
B = set()
for a in A:
if(a>=0):
B.add(a)
B = list(B)
B.sort()
if(len(B)==0):
return 0
if(B[0]!=0):
return 0
mex = 0
for i in range(1,len(B)):
if(B[i]==B[i-1]+1):
mex+=1
else:
break
return mex+1
def GCD(a,b): #ab
return math.gcd(a,b)
def LCM(a,b): #ab
return a*b//GCD(a,b)
def fact_L(n,mod): # [0!, 1! ..., n!]
fact = [1]
p = 1
for i in range(1,n+1):
p *= i
p %= mod
fact.append(p)
return fact
def bitCount_L(n): # nbit
bitcount = [0] * (n+1)
for i in range(1,n+1):
bitcount[i] = bitcount[i//2] + i%2
return bitcount
def factorial(n, m=0): #n | m:mod()
if(n<0):
return -1
elif(n==0):
return 1
P = 1
for i in range(1,n+1):
P *= i
if(m==0):
continue
P %= m
return P
def nPr(n, r, m=0): #nPr
if(n<=0 or r<0 or n<r):
return -1
if(r==0):
return 1
P = 1
for i in range(n,n-r,-1):
P *= i
if(m==0):
continue
P %= m
return P
def nCr(n, r, m=0): #nCr
if(n<r):
return 0
if(n==r):
return 1
if(n<=0 or r<0 or n<r):
return -1
N = 1
for i in range(r):
N *= n-i
if(m==0):
continue
N %= m
R = factorial(r)
return N//R
def nCrm(n,r,m=mod): #nCr%mod
if(n<r):
return 0
if(n==r):
return 1
if(n<=0 or r<0 or n<r):
return -1
over=1
for i in range(n-r+1,n+1):
over *= i
over %= m
under=1
for i in range(1,r+1):
under *= i
under %= m
return over*pow(under,m-2,m)%m
def is_prime(n): # => True/False
if n == 2:
return 1
if n == 1 or n%2 == 0:
return 0
m = n - 1
lsb = m & -m
s = lsb.bit_length()-1
d = m // lsb
test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for a in test_numbers:
if a == n:
continue
x = pow(a,d,n)
r = 0
if x == 1:
continue
while x != m:
x = pow(x,2,n)
r += 1
if x == 1 or r == s:
return 0
return 1
def prime_L(n): #n
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if not is_prime[i]:
continue
for j in range(i * 2, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
def find_prime_factor(n):
if n%2 == 0:
return 2
m = int(n**0.125)+1
for c in range(1,n):
f = lambda a: (pow(a,2,n)+c)%n
y = 0
g = q = r = 1
k = 0
while g == 1:
x = y
while k < 3*r//4:
y = f(y)
k += 1
while k < r and g == 1:
ys = y
for _ in range(min(m, r-k)):
y = f(y)
q = q*abs(x-y)%n
g = math.gcd(q,n)
k += m
k = r
r *= 2
if g == n:
g = 1
y = ys
while g == 1:
y = f(y)
g = math.gcd(abs(x-y),n)
if g == n:
continue
if is_prime(g):
return g
elif is_prime(n//g):
return n//g
else:
return find_prime_factor(g)
def primeFactorization_2L(n): #2n => [[, ], ...]2
if(n<=10**6):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
else:
res = {}
while not is_prime(n) and n > 1:
p = find_prime_factor(n)
s = 0
while n%p == 0:
n //= p
s += 1
res[p] = s
if n > 1:
res[n] = 1
R = []
for r in res:
R.append([r,res[r]])
R.sort()
return R
def divisor_L(n): #n
if(n==1):
return [1]
if(n<=10**6):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
else:
L = primeFactorization_2L(n)
E = [[]for i in range(len(L))]
for i in range(len(L)):
for j in range(L[i][1]+1):
E[i].append(L[i][0]**j)
D = []
for p in list(itertools.product(*E)):
s = 1
for v in p:
s *= v
D.append(s)
D.sort()
return D
def floorsqrt(n): # N => ⌊√N⌋
# only for n <= 10 ** 18
ok = 10 ** 9 + 10
ng = 0
while ok - ng > 1:
t = (ok + ng) // 2
if t * t > n: ok = t
else: ng = t
return ng
def decimal_to_nAry(num_10,n): #10n(n<=36) |int => str
str_n = []
while num_10:
if num_10%n >= 10:
str_n.append(chr(num_10%n+55))
else:
str_n.append(str(num_10%n))
num_10 //= n
return "".join(str_n[::-1])
def nAry_to_decimal(X,n): #n10(n<=36) | str => int
num = 0
X = X.upper()
X = list(X)
for i in range(len(X)):
if(("0"<=X[i]<="9")==False):
X[i] = str(ord(X[i]) - 55)
for i in range(1,len(X)+1):
num += int(X[-i]) * pow(n, (i-1))
return num
def roundOff(x,d): # x:, d:(|) => float
return float(Decimal(x).quantize(Decimal(f"1E{d}"), rounding=ROUND_HALF_UP))
def dsin(d): #sin
return math.sin(math.radians(d))
def dcos(d): #cos
return math.cos(math.radians(d))
def rotate(x,y,d,cx=0,cy=0): #P(x,y)A(cx,cy) => [x,y]
nx = (x-cx)*dcos(d)-(y-cy)*dsin(d)
ny = (x-cx)*dsin(d)+(y-cy)*dcos(d)
return [nx+cx,ny+cy]
def findAngle(O,A,B): #∠AOB()
s = [A[0]-O[0],A[1]-O[1]]
t = [B[0]-O[0],B[1]-O[1]]
u = s[0]*t[0]+s[1]*t[1]
l = (s[0]**2+s[1]**2)**(1/2) * (t[0]**2+t[1]**2)**(1/2)
v = u/l
t = math.degrees(math.acos(v))
return t
def outerProduct(Av,Bv): #(=)(a×b)
return Av[0]*Bv[1] - Bv[0]*Av[1]
def CCW(O,A,B): #OAAB
# -1: , 0: , 1:
s = [A[0]-O[0],A[1]-O[1]]
t = [B[0]-O[0],B[1]-O[1]]
op = outerProduct(s,t)
if(op > 0): return 1
if(op < 0): return -1
if(op == 0): return 0
def matrixMultiplication_2D(a,b,m): #(a×b) m:mod
I,J,K,L = len(a),len(b[0]),len(b),len(a[0])
if(L!=K):
return -1
c = [[0] * J for _ in range(I)]
for i in range(I) :
for j in range(J) :
for k in range(K) :
c[i][j] += a[i][k] * b[k][j]
c[i][j] %= m
return c
def matrixExponentiation_2D(x,n,m): # (x^n) m:mod
y = [[0] * len(x) for _ in range(len(x))]
for i in range(len(x)):
y[i][i] = 1
while n > 0:
if n & 1:
y = matrixMultiplication_2D(x,y,m)
x = matrixMultiplication_2D(x,x,m)
n >>= 1
return y
def twoCircles(A,B): # | [x,y(=),r(=)]
# 1 : 2
# 2 : 2
# 3 : 2
# 4 : 2 2
# 5 : 2 2
x1 = A[0]
x2 = B[0]
y1 = A[1]
y2 = B[1]
r1 = A[2]
r2 = B[2]
d = abs((x1-x2)+1j*(y1-y2))
if(abs(r2-r1)>d):
return 1
elif(abs(r2-r1)==d):
return 2
elif(r1+r2>d):
return 3
elif(r1+r2==d):
return 4
elif(r1+r2<d):
return 5
######
def TS(_str): #/
print('{}: {}'.format(_str, eval(_str)))
def T2d(A): #
for a in A:
print(*a)
def T3d(A): #
for a in A:
T2d(a)
BR()
def BR(): #
print("---")
#----------------------------------------------------------------------
#-----------------------------------------------------------
'''
######
ceil(a,b): #
div(a,b,p): #mod pa/b(bp)
transpose(A): #
removeDuplicates_2D(A): #
cumulativeSum_1D(A) #A
cumulativeSum_2D(S): #S =>
string_to_runLength(S: str) #/ => [(,), ...]
runLength_to_string(L: "list[tuple]") # =>
bfs(i,G,m = mod) # i: m:mod(998244353) => dist,pre,dp
dijkstra(s,G): #s: => cost,pre | G:(,)
coordinates(A) # ( : ),2(: ),
eng_L() #
ENG_L() #
bit_len(n): #bit
bit_cnt(n): # bit1
idx_le(A, x) # x / "No"
idx_lt(A, x) # x / "No"
idx_ge(A, x) # x / "No"
idx_gt(A, x) # x / "No"
cnt_le(A, x) # x
cnt_lt(A, x) # x
cnt_ge(A, x) # x
cnt_gt(A, x) # x
###/###
def allAnd(A): # AAND
def allOr(A): # AOR
def allXor(A): # AXOR
MEX(A) #AMEX
GCD(a,b) #ab
LCM(a,b) #ab
fact_L(n,mod): # [0!, 1! ..., n!]
bitCount_L(n): # nbit
factorial(n,m) #n | m:mod()
nPr(n,r,m) #nPr | m:mod()
nCr(n,r,m) #,nCr | m:mod()
nCrm(n,r,m) #nCr%mod
divisor_L(n) #n
is_prime(n) # => True/False
prime_L(n) #n
primeFactorization_2L(n) #2n => [[, ], ...]2
floorsqrt(n): # N => ⌊√N⌋
decimal_to_nAry(num_10,n) #10n(n<=36) |int => str
nAry_to_decimal(num_n,n) #n10(n<=36) | str => int
roundOff(x,d): # x:, d:(|) => float
dsin(d): #sin
dcos(d): #cos
rotate(x,y,d,cx,cy): #P(x,y)A(cx,cy)() => [x,y]
findAngle(O,A,B) #∠AOB() | [x,y(=)]
outerProduct(Av,Bv) #(=)(a×b) | [x,y(=)]
CCW(O,A,B) #OAAB
=> -1:, 0:, 1: | [x,y(=)]
matrixMultiplication_2D(a,b,m) #(a×b) m:mod |
matrixExponentiation_2D(x,n m)# (x^n) m:mod |
twoCircles(A,B): # | [x,y(=),r(=)]
=> 1, 2, 3, 4, 5
######
TS(_str) # / => :××
T2d(A): #
T3d(A): #
BR() #
######
|S|<x => "0"*(x-|S|) + S : str(n).zfill(x)
str.upper()
str.lower()
str.capitalize()
:str.title()
str.swapcase()
→ ASCII ord(s)
ASCII chr(x)
ASCII
65:A ~ 90:Z
97:a ~ 122:z
'''
#PyPy----------------------------------
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
#----------------------------------------------------------------------------
a,b = MI()
c,d = MI()
print(a*c-b*d, a*d+b*c)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0