結果

問題 No.2589 Prepare Integers
ユーザー hirayuu_ychirayuu_yc
提出日時 2023-12-16 22:40:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,720 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 79,920 KB
最終ジャッジ日時 2024-09-27 07:52:11
合計ジャッジ時間 8,385 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 100 ms
77,180 KB
testcase_01 AC 48 ms
62,232 KB
testcase_02 AC 46 ms
60,664 KB
testcase_03 AC 38 ms
54,168 KB
testcase_04 AC 969 ms
79,412 KB
testcase_05 AC 583 ms
78,920 KB
testcase_06 AC 421 ms
79,204 KB
testcase_07 AC 355 ms
79,084 KB
testcase_08 AC 266 ms
78,648 KB
testcase_09 AC 276 ms
79,872 KB
testcase_10 AC 275 ms
79,368 KB
testcase_11 AC 297 ms
79,596 KB
testcase_12 WA -
testcase_13 RE -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 AC 277 ms
78,764 KB
testcase_20 RE -
testcase_21 WA -
testcase_22 WA -
testcase_23 RE -
testcase_24 AC 296 ms
79,920 KB
testcase_25 AC 290 ms
78,728 KB
testcase_26 RE -
testcase_27 AC 238 ms
78,612 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]
    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
            if g==0:
                g=K
            div=gcd(g,K)
            rev=pow(g//div,-1,K)
            g=div
            for j in range(len(v)):
                v[j]=(v[j]*rev)%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