結果

問題 No.2589 Prepare Integers
コンテスト
ユーザー hirayuu_yc
提出日時 2023-12-16 23:24:34
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,600 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 79,808 KB
最終ジャッジ日時 2024-09-27 07:52:19
合計ジャッジ時間 6,015 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 3
other AC * 10 WA * 2 RE * 12
権限があれば一括ダウンロードができます

ソースコード

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)):
        if a[i]==0:
            a[i]=K
        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