結果

問題 No.2589 Prepare Integers
ユーザー 👑 p-adic
提出日時 2023-12-17 23:52:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 276 ms / 2,000 ms
コード長 2,471 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 80,156 KB
最終ジャッジ日時 2024-09-27 08:11:48
合計ジャッジ時間 6,701 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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 ):
    L=len(exp)-1
    if gcd_inv[L]==0:
        gcd[L][L]=PartitionOfUnity(K,exp[L],K)
        gcd_inv[L]=K//gcd[L][L]
        for d in R(L):
            gcd[L][d] , exp[d] = exp[d]*u1%K , exp[d]*gcd_inv[L]%K
    else:
        gcd[L][L]=PartitionOfUnity(gcd[L][L],exp[L],K)
        gcd_inv[L]=K//gcd[L][L]
        for d in R(L):
            gcd[L][d] , exp[d] = ( gcd[L][d] * u0 + exp[d] * u1 ) % K , ( gcd[L][d] * v0 + exp[d] * v1 ) % K
    exp.pop()
    while len(exp) and exp[-1] == 0:exp.pop()
    if len(exp):SetGcd(gcd,gcd_inv,exp,K)
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]
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 )
    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:
                r = exp[l] - lb[l]
                if r < 0:break
                if r > 0 or l==0:
                    coef[l]=1
                    break
            else:
                r = exp[l] - lb[l] % gcd[l][l]
                if r < 0:break
                coef[l] = r // gcd[l][l]
                r %=gcd[l][l]
                if r > 0:
                    coef[l]+=1
                    break
                elif l==0:
                    coef[l]+=1
                    break
                diff = ( coef[l] - lb[l] // gcd[l][l] ) % K
                for d in R(l+1):lb[d] = ( lb[d] + diff * gcd[l][d] ) % K
        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 )
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0