We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 * 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
全数字的乘积
如果一个 n 位数包含了 1 至 n 的所有数字恰好一次,我们称它为全数字的;例如,五位数 15234 就是 1 至 5 全数字的。
7254 是一个特殊的乘积,因为在等式 39 * 186 = 7254 中,被乘数、乘数和乘积恰好是 1 至 9 全数字的。
找出所有被乘数、乘数和乘积恰好是 1 至 9 全数字的乘法等式,并求出这些等式中乘积的和。
注意:有些乘积可能从多个乘法等式中得到,但在求和的时候只计算一次。
根据数字的特点,这个乘积必为四位数,原因如下:
- 如果它为三位数,那么另外六个数字构成的乘积(考虑 11111 * 1)必定大于它
- 如果它为五位数,那么另外四个数字构成的乘积(考虑 99 * 99 = 9801)必定小于它
同时,乘数只可能是 14 或 23 组合,也就是说我们对于给定的四位数只需要在 0 ~ 100 内寻找因数,然后根据因数判断是否符合条件即可。
(defun eu32-nums2str (i j p)
(mapconcat
'char-to-string
(sort (append (concat (number-to-string i)
(number-to-string j)
(number-to-string p))
nil)
'<)
""))
(my-time
(let ((res))
(cl-loop
for i from 1000 to 9999
do (cl-loop
for j from 2 to 99
do (when (= 0 (% i j))
(let ((k (/ i j)))
(when (string= "123456789" (eu32-nums2str i j k))
(push i res)
(cl-return))))))
res))
;;0.23797607421875s
=> (7852 7632 7254 6952 5796 5346 4396)
(+ 7852 7632 7254 6952 5796 5346 4396)
=> 45228
当然,判断部分可以优化一下(好像没什么用):
(defun eu32-isok (a b c)
(let ((s (mapconcat 'number-to-string `(,a ,b ,c))))
(when (not (cl-find ?0 s))
(let ((v (make-vector 9 0)))
(cl-loop for a across s
do (cl-incf (aref v (- a ?1))))
(cl-loop for a across v
if (/= a 1)
return nil
finally return t)))))
(my-time
(let ((res))
(cl-loop
for i from 1000 to 9999
do (cl-loop
for j from 2 to 99
do (when (= 0 (% i j))
(let ((k (/ i j)))
(when (eu32-isok i j k)
(push i res)
(cl-return))))))
res))
(7852 7632 7254 6952 5796 5346 4396)
;;0.24508309364318848s
当然了,判断可能还有更高效的方法,以下方法来自问题 32 的讨论区:
(defun eu32-isok2 (a b c)
(let ((v (make-vector 10 0)))
(cl-block nil
(while (/= a 0)
(when (or (= (% a 10) 0)
(> (cl-incf (aref v (% a 10))) 1))
(cl-return nil))
(setq a (/ a 10)))
(while (/= b 0)
(when (or (= (% b 10) 0)
(> (cl-incf (aref v (% b 10))) 1))
(cl-return nil))
(setq b (/ b 10)))
(while (/= c 0)
(when (or (= (% c 10) 0)
(> (cl-incf (aref v (% c 10))) 1))
(cl-return nil))
(setq c (/ c 10)))
(cl-incf (aref v 0))
(equal [0 1 1 1 1 1 1 1 1 1] v))))