考虑如下冰雹序列的变体：

初值为$a_1$

若$a_n$能被3整除，则$a_{n+1}=a_n/3$，记这样的操作为D。

若$a_n$模3余1，则$a_{n+1}=(4a_n+2)/3$，记这样的操作为U。

若$a_n$模3余2，则$a_{n+1}=(2a_n-2)/3$，记这样的操作为d。

反复递推直到$a_n=1$为止。

给定初值，可以列出其操作步骤对应的字符串：

例如，若$a_1=231$，则数列为$231\to77\to51\to17\to11\to7\to10\to14\to9\to3\to1$，对应的操作步骤是DdDddUUdDD。

当然，也存在其它的整数数列，其操作步骤同样以DdDddUUdDD….开头。例如，若$a_1=1004064$时，操作步骤是DdDddUUdDDDdUDUUUdDdUUDDDUdDD。

事实上，1004064也是在超过一百万的初值中最小的操作步骤以DdDddUUdDD开头的数。

求超过$10^{15}$的初值中最小的操作步骤以UDDDUdddDDUDDddDdDddDDUDDdUUDd开头的数。

本题难度:

解答

设x是一个满足要求的初值，经过这一系列操作后所得的数是y，则容易验证 $$y=\frac{4194304}{3^{30}}x-\frac{21110037246199}{3^{30}},$$ 其中30是操作步骤字符串UDDDUdddDDUDDddDdDddDDUDDdUUDd的长度。整理后得 $$4194304x-3^{30}y=21110037246199,$$ 用辗转相除法即可解得结果$1125977393124310$。

from fractions import Fraction

def extGCD(a,b):
    if b==0:return a,1,0
    d,x,y=extGCD(b,a%b)
    return d,y,x-(a//b)*y
    
k,b=Fraction(1),Fraction(0)
for c in "UDDDUdddDDUDDddDdDddDDUDDdUUDd":
    if c=="U":
        k=k*4/3
        b=(b*4+2)/3
    elif c=="D":
        k=k/3
        b=b/3
    else:
        k=k*2/3
        b=(b*2-1)/3

a,b,c=k.numerator,b.denominator,-b.numerator
d,x,y=extGCD(a,b)
x=x*c%b

print(x+(10**15-x+b-1)//b*b)