将乘数记作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
|