結果

問題 No.2589 Prepare Integers
ユーザー hirayuu_ychirayuu_yc
提出日時 2023-12-16 23:15:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,558 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,204 KB
実行使用メモリ 79,736 KB
最終ジャッジ日時 2024-09-27 07:52:30
合計ジャッジ時間 10,132 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 104 ms
77,292 KB
testcase_01 AC 46 ms
62,056 KB
testcase_02 AC 44 ms
61,376 KB
testcase_03 AC 40 ms
53,268 KB
testcase_04 AC 937 ms
79,736 KB
testcase_05 AC 616 ms
78,708 KB
testcase_06 AC 415 ms
78,732 KB
testcase_07 AC 385 ms
78,824 KB
testcase_08 AC 292 ms
79,692 KB
testcase_09 AC 287 ms
79,284 KB
testcase_10 AC 290 ms
78,772 KB
testcase_11 AC 295 ms
78,964 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 289 ms
79,588 KB
testcase_18 WA -
testcase_19 AC 286 ms
78,632 KB
testcase_20 AC 284 ms
79,384 KB
testcase_21 WA -
testcase_22 AC 303 ms
78,296 KB
testcase_23 AC 311 ms
79,036 KB
testcase_24 AC 300 ms
78,956 KB
testcase_25 AC 303 ms
79,360 KB
testcase_26 AC 293 ms
79,684 KB
testcase_27 AC 242 ms
78,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd
def f(x,y):
    ret=0
    pl=1
    for i in range(L):
        ret+=pl*((x+y)%K)
        x//=K
        y//=K
        pl*=K
    return ret

def power(x,y):
    ret=0
    pl=1
    for i in range(L):
        ret+=pl*(x*y%K)
        x//=K
        pl*=K
    return ret

def get(x,y):
    return (x//pow(K,y))%K

def ext_gcd(a,b):
    if a==b==0:
        return 0,0
    g=gcd(a,b)
    a//=g
    b//=g
    hist=[]
    while b>0:
        hist.append((a,b))
        a,b=b,a%b
    x=a
    y=0
    while len(hist)>0:
        a,b=hist.pop()
        x,y=y,x-(a//b)*y
    return x,y

def many_ext(a):
    x=[0]*len(a)
    x[0]=1
    g=a[0]
    if a[0]==0:
    	g=K
    for i in range(1,len(a)):
        u,v=ext_gcd(g,a[i])
        x[i]=v
        for j in range(i):
            x[j]*=u
            x[j]%=K
        g=gcd(g,a[i])
    return x,g

K,Q=map(int,input().split())
L=0
lg=1
while lg<=10**9:
    lg*=K
    L+=1
G=[0]*L
for _ in range(Q):
    t,x=map(int,input().split())
    if t==1:
        B=[x]
        for i in range(L-1,-1,-1):
            X=[get(G[i],i)]
            for j in B:
                X.append(get(j,i))
            v,g=many_ext(X)
            s=0
            for j in range(len(X)):
                s+=X[j]*v[j]
                s%=K
            T=power(G[i],v[0])
            for j in range(len(v)-1):
                T=f(T,power(B[j],v[j+1]))
            B=[G[i]]+B
            for j in range(len(X)):
                B[j]=f(B[j],power(T,-X[j]//g))
            G[i]=T
    elif t==2:
        C=[1]*(L+1)
        D=[1]*L
        for i in range(1,L+1):
            if G[i-1]==0:
                C[i]=C[i-1]
            else:
                C[i]=C[i-1]*(K//get(G[i-1],i-1))
                D[i-1]=K//get(G[i-1],i-1)
        if x>C[L]:
            print(-1)
            continue
        X=x-1
        Y=0
        for i in range(L-1,-1,-1):
            X,Y=X%C[i],f(Y,power(G[i],X//C[i]-get(Y,i)//(K//D[i])))
        print(Y)
    else:
        X=0
        Y=0
        C=[1]*(L+1)
        D=[1]*L
        for i in range(1,L+1):
            if G[i-1]==0:
                C[i]=C[i-1]
            else:
                C[i]=C[i-1]*(K//get(G[i-1],i-1))
                D[i-1]=K//get(G[i-1],i-1)
        if pow(K,L)-1<=x:
            print(C[L])
            continue
        for i in range(L-1,-1,-1):
            r=get(X,i)%(K//D[i])
            d=get(x+1,i)
            Y+=((d-r+(K//D[i])-1)//(K//D[i]))*C[i]
            if (d-r)%(K//D[i])!=0:
                break
            X=f(X,power(G[i],(d-get(X,i))//(K//D[i])))
        print(Y)
0