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 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 ) l_last = -1 for l in R(L,-1,-1): if gcd[l][l] == 0: if exp[l] > lb[l]: coef[[l_last,l][l_last<0]]+=1 break else: if gcd_inv[l]>0:l_last=l 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 )