0170 乘积拼接
* * * *
拉格朗日计划
* * * *
乘积拼接

将6分别乘以1273和9854得 \begin{align*} 6\times 1273&=7638 \\ 6\times 9854&=59124 \end{align*} 连接这两个乘积得到1至9的全数字数763859124。称763859124为“6和(1273,9854)乘积的拼接”。注意到,被乘的这些数的拼接612739854同样也是1至9的全数字数。

对于0至9全数字数也存在同样的可能。

考虑由一个整数和另外至少两个整数的乘积拼接而成的数、以及被乘的整数本身拼接而成的数,且两者都是是0至9的全数字数的情况,求这些全数字数中最大的一个。

本题难度:



解答

将乘数记作x(例如上例中$x=6$),显然有$x>1$。

若$a, b$是两整数,记$a\oplus b$为a与b拼接所得的整数,则有 $$x\times (a\oplus b)=(x\times a)\oplus(x times b),$$ 因此可以不失一般性地假设只有两个被乘数a、b。

注意到任何0到9的全数字数都能被3整除($0+1+\ldots+9=45$)因此3也能整除x和$a\oplus b$中的至少一个。

又因为x的各位数字之和即45减去$a\oplus b$的数字之和,从而两者中只要有一个能被3整除,则另一个也能被3整除,因此事实上两者都能被3整除。

接下来大胆猜测最大数的首两位是98并据此搜索(若无结果则再以97为首两位搜索,以次类推)。

枚举剩余八个数字的全部排列,对每个排列,枚举将其拆分为两个数字x、y的所有七种可能,若$d=\gcd(x,y)$能被$3$整除,再找出d的所有大于1的约数j,并检查$x/j, y/j, j$是否能构成全数字数。

结果是$985716=27\times 36508$与$4023=27\times 149$的拼接,即$9857164023$。

import itertools,fractions

a=sorted(itertools.permutations("01234567",8),reverse=True)

found=False
i=0
while not found and i < len(a):
    c=a[i]
    for p in range(1,8):
        x,y=int("98"+"".join(c[:p])),int("".join(c[p:]))
        d=fractions.gcd(x,y)
        if d%3==0:
            f=[d]
            j=2
            while j*j<=d:
                if d%j==0:
                    f.append(j)
                    f.append(d/j)
                j+=1
            for j in f:
                z=str(x/j)+str(y/j)+str(j)
                if len(set(z))==len(z)==10:
                    print "98"+"".join(c),x,y,x/j,y/j,j,d,f
                    found=True
    i+=1