結果

問題 No.2589 Prepare Integers
ユーザー 👑 p-adicp-adic
提出日時 2023-12-17 19:39:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,744 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 79,776 KB
最終ジャッジ日時 2024-09-27 08:02:45
合計ジャッジ時間 7,693 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
59,688 KB
testcase_01 AC 44 ms
58,804 KB
testcase_02 AC 42 ms
59,660 KB
testcase_03 AC 45 ms
58,596 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 243 ms
79,504 KB
testcase_10 AC 260 ms
79,184 KB
testcase_11 AC 248 ms
78,288 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 247 ms
79,620 KB
testcase_25 AC 240 ms
79,212 KB
testcase_26 AC 245 ms
79,044 KB
testcase_27 AC 190 ms
78,092 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
x=0
def Expand( X , digit ):
	global x
	answer=[]
	for d in R(digit):
		if x==0:break
		if X[d]!=0:
			answer+=[x%X[d]]
			x//=X[d]
		else:answer+=[0]
	return answer

u0=u1=v0=v1=0
def PartitionOfUnity( b_0 , b_1 , K ):
	global u0 , u1 , v0 , v1
	a=[[1,0],[0,1]]
	b=[b_0,b_1]
	i_0=b_0<b_1
	i_1=1-i_0
	while b[i_1]!=0:
		q=b[i_0]//b[i_1]
		a[i_0][i_0]=(a[i_0][i_0]-q*a[i_1][i_0])%K
		a[i_0][i_1]=(a[i_0][i_1]-q*a[i_1][i_1])%K
		b[i_0]-=q*b[i_1]
		i_0,i_1=i_1,i_0
	u0,u1,v0,v1=a[i_0][0],a[i_0][1],a[i_1][0],a[i_1][1]
	return b[i_0]

def SetGcd( gcd , gcd_inv , exp , K , euler_minus ):
	L=len(exp)-1
	if gcd_inv[L]==0:
		gcd[L][L]=PartitionOfUnity(exp[L],K,1)
		gcd_inv[L]=K//gcd[L][L]
		r=exp[L]//gcd[L][L]
		r_inv=pow(r,euler_minus,K)
		for d in R(L):gcd[L][d]=r_inv*exp[d]%K
		return
	gcd[L][L]=PartitionOfUnity(gcd[L][L],exp[L],K)
	gcd_inv[L]=K//gcd[L][L]
	exp.pop()
	for d in R(L):
		temp0 = ( gcd[L][d] * u0 + exp[d] * u1 ) % K
		temp1 = ( gcd[L][d] * v0 + exp[d] * v1 ) % K
		gcd[L][d] = temp0
		exp[d] = temp1
	while len(exp) and exp[-1] == 0:exp.pop()
	if len(exp):SetGcd(gcd,gcd_inv,exp,K,euler_minus)

O=print
J=lambda:map(int,input().split())
K,Q=J()
digit = 0
K_vec=[]
power = K*10**18
while power > 0:
	power //= K
	digit+=1
	K_vec+=[K]
euler_minus=1
K_copy = K
for p in R(2,31623):
	if K_copy%p == 0:
		euler_minus *= p-1
		K_copy//=p
		while K_copy%p == 0:
			euler_minus *= p
			K_copy//=p
if K_copy>1:euler_minus*=K_copy-1
euler_minus-=1
gcd=[[0]*(d+1)for d in R(digit)]
gcd_inv=[0]*digit
for q in R(Q):
	type,x=J()
	if type==1:
		exp=Expand(K_vec,digit)
		SetGcd( gcd , gcd_inv , exp , K , euler_minus )
	elif type == 2:
		if x == 1:
			O(0)
			continue
		x-=1
		exp = Expand( gcd_inv , digit )
		if x > 0:
			O( -1 )
			continue
		L=len(exp)-1
		coef=[0]*( L + 1 )
		for l in R(L,-1,-1):
			if gcd[l][l] != 0:
				exp[l] = (exp[l] - coef[l] // gcd[l][l])%K
				for d in R(l+1):
					coef[d] = ( coef[d] + exp[l] * gcd[l][d] ) % K
		answer = 0
		power = 1
		for d in R(L+1):
			answer += coef[d] * power
			power *= K
		O( answer )
	elif type == 3:
		if x == 0:
			O( 1 )
			continue
		exp = Expand( K_vec , digit )
		L = len(exp) - 1
		coef=[0]*( L + 1 )
		lb=[0]*( L + 1 )
		for l in R(L,-1,-1):
			if gcd[l][l] == 0:
				if exp[l] > lb[l]:
					coef[l]+=1
					break
			else:
				r = exp[l] - lb[l] % gcd[l][l]
				if r < 0:
					coef[l+1]-=1
					break
				coef[l] = r // gcd[l][l]
				if r % gcd[l][l] != 0:
					coef[l]+=1
					break
				r = ( coef[l] - lb[l] // gcd[l][l] ) % K
				for d in R(l+1):
					lb[d] = ( lb[d] + r * gcd[l][d] ) % K
			if l == 0:
				coef[l]+=1
				break
		answer = 0
		prod = 1
		for d in R(L+1):
			answer += coef[d] * prod
			if gcd_inv[d] != 0:
				prod *= gcd_inv[d];
		O( answer )
0