题目32：找出所有能写成 pandigital 数字乘积的数字之和

欧拉计划

Pandigital products

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 中每个数字且只使用了一次，我们称其为 pandigital。例如，15234 这个五位数，是 1 到 5 pandigital 的。

7254 是一个不寻常的数，因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了一个1到 9 的 pandigital 组合。

找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。

提示: 有的乘积数字能够被多个乘法算式得到，所以在计算时要记得只计算它们一次。

wenzhong

额

迷雾少年

4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632

bool mycalc(int a,int b,int c)
{
        string myResult;
        char buf[25];
        itoa(a,buf,10);
        myResult+=buf;
        itoa(b,buf,10);
        myResult+=buf;
        itoa(c,buf,10);
        myResult+=buf;


        
        sort(myResult.begin(),myResult.end());
        return myResult==string("123456789");
        
}
int main() 
{ 
    for (int n=2;n<=100000;n++)
    {
                for (int m=2;m<=100000;m++)
                {
                        int mul = n*m;
                        if(mycalc(m,n,mul))
                        {
                                std::cout<<n<<"*"<<m<<"="<<mul<<endl;
                        }
                }
    }
        return 0;
        
} 

愤怒的大头菇

list1 = [1,2,3,4,5,6,7,8,9]
list2 = []
for i in range(1,100):
      for j in range(100,10000):
            temp = True
            if len(str(i))+len(str(j))+len(str(i*j)) == 9:
                  for each in list1:
                        if str(each) not in (str(i)+str(j)+str(i*j)):
                              temp = False
                              break
                  if temp:
                        if i*j not in list2:
                              list2.append(i*j)
print(sum(list2))

结果:45228

jerryxjr1220

楼上答案正确：45228

def pan(n): return len(n)==9 and "123456789".strip(n)==""

prod = set()
for i in range(1,10):
    for j in range(1234,9877):
        if pan(str(i)+str(j)+str(i*j)): prod.add(i*j)

for i in range(12,99):
    for j in range(123,988):
        if pan(str(i)+str(j)+str(i*j)): prod.add(i*j)

print (sum(prod))

芒果加黄桃

# encoding:utf-8
# pandigital 之和
from time import time 
def isDup(N):
    if str(N).find('0') > -1 :
        return False
    if len(str(N)) == len(set(str(N))):
        return True
    return False
def isPanDigital(n1, n2, n3):
    l_t = []
    l_t.extend(list(str(n1)))
    l_t.extend(list(str(n2)))
    l_t.extend(list(str(n3)))
    l_t = set(l_t)
    if len(l_t) == 9:
        return True
    return False
def euler032():
    l_result = []
    for i in range(1, 10):
        for j in range(1234, 9877):
            if isDup(j):
                k = i * j 
                if k > 9876:
                    break
                if isDup(k):
                    if isPanDigital(i, j, k):
                        #print(i, j, k)
                        l_result.append(k)
    for i in range(12, 99):
        for j in range(123, 988):
            if isDup(j):
                k = i * j 
                if k > 9876:
                    break
                if isDup(k):
                    if isPanDigital(i, j, k):
                        #print(i, j, k)
                        l_result.append(k)                    
    print(sum(set(l_result)))            
if __name__ == '__main__':
    start = time() 
    # print(isDup(121))
    euler032()
    print('cost %.6f sec' % (time() - start))

45228
cost 0.078008 sec

渡风

时间已过 30.829161 秒。
此代码使用matlab编程
Problem32所用时间为30.8314秒
Problem32的答案为45228

%% Problem32
%找出所有能写成pandigital 数字的乘积之和
function Output = Problem32()
tic

value = [1 2 3 4 5 6 7 8 9];
Judge = value * value';

Record = [];
All = perms([1 2 3 4 5 6 7 8 9]);
[M, ~] = size(All);
for aa = 1:M
      %tempvector = str2num(num2str(aa)')';
      tempvector = All(aa, :);
      disp(tempvector)
     if tempvector * tempvector' == Judge
         t = tempvector;
         a = t(1);
         b = 1000*t(2) + 100*t(3) +10*t(4) + t(5);
         c = 1000*t(6) + 100*t(7) +10*t(8) + t(9);       
         if a * b == c
             Record = union(Record, c);
         end
         d = t(1)*10 + t(2);
         e = 100*t(3) + 10*t(4) +t(5); 
         f = 1000*t(6) + 100*t(7) + 10*t(8) + t(9);    
         if d * e == f
             Record = union(Record, f);
         end 
     else
         continue
     end 
end

toc

Output = sum(Record);
disp('此代码使用matlab编程')
disp(['Problem32所用时间为',num2str(toc),'秒'])
disp(['Problem32的答案为',num2str(Output)])

JonTargaryen

#include <stdio.h>

int is_pandigital(int a, int b, int product);

int main()
{
    int a, b, product;
    int sum = 0;
    int results[128] = {0};
    int i = 0, j;
    int flag = 1;

    for(a = 1; a < 1024 / 2; a++)
    {
        for(b = a; b < 4096; b++)
        {
            product = a * b;

            if(is_pandigital(a, b, product))
            {
                for(j = 0; j < i; j++)
                {
                    if(results[j] == product)
                    {
                        flag = 0;
                    }
                }

                if(flag)
                {
                    results[i] = product;
                    sum += product;
                    printf("%d * %d = %d\n", a, b, product);
                    i++;
                }

                flag = 1;
            }
        }
    }

    printf("\n%d\n", sum);

    return 0;
}

int is_pandigital(int a, int b, int product)
{
    int count = 0;
    int flag[10] = {0};
    int i;

    while(a > 0)
    {
        flag[a % 10]++;
        a /= 10;
        count++;
        if(count > 9)
        {
            return 0;
        }
    }

    while(b > 0)
    {
        flag[b % 10]++;
        b = b / 10;
        count++;
        if(count > 9)
        {
            return 0;
        }
    }

    while(product > 0)
    {
        flag[product % 10]++;
        product = product / 10;
        count++;
        if(count > 9)
        {
            return 0;
        }
    }

    for(i = 1; i < 10; i++)
    {
        if(flag[i] != 1)
        {
            return 0;
        }
    }

    return 1;
}

JonTargaryen

JonTargaryen 发表于 2017-5-23 19:54

def is_pandigital(a, b, product):
    flag = [0] * 10
    count = 0

    while a > 0:
        flag[a % 10] += 1
        a //= 10
        count += 1
        if count > 9:
            return 0

    while b > 0:
        flag[b % 10] += 1
        b //= 10
        count += 1
        if count > 9:
            return 0

    while product > 0:
        flag[product % 10] += 1
        product //= 10
        count += 1
        if count > 9:
            return 0

    for each in flag[1:]:
        if each != 1:
            return 0

    return 1

def main():
    results = []
    answer = 0

    for a in range(1, 512):
        for b in range(a, 4096):
            product = a * b

            if is_pandigital(a, b, product):
                for each in results:
                    if each == product:
                        flag = 0

                if flag:
                    results.append(product)
                    answer += product
                    print("%d * %d = %d" %(a, b, product))

            flag = 1

    print(answer)

    return

if __name__ == '__main__':
    main()

由我们主宰

import java.util.Arrays;
public class PandigitalProducts{
        public static void main(String[] args){
                int[] m = new int[3];
                int[] n = new int[4];
                int[] result = new int[10];
                int[] consequence = new int[10];
                int r = 0,sum = 0;
                int count_1 = 0,count_2 = 0,count_3 = 0;
                int i = 0;
                for(int a = 1;a < 100;a ++){
                        count_1 = Record(m,a);
                        if(Repeat(m,count_1)){
                                continue;
                        }
                        for(int b = 101;b < 10000;b ++){
                                count_2 = Record(n,b);
                                if( Repeat(n,count_2) ){
                                        continue;
                                }
                                if(Pandigital(m,n,count_2) ){
                                        r = a * b;
                                        count_3 = Record(result,r);
                                        if(Repeat(result,count_3) || count_1+count_2+count_3 != 9){
                                                continue;
                                        }
                                        if(Pandigital(result,m,count_1) && Pandigital(result,n,count_2)){
                                                Arrays.sort(consequence);
                                                if(Arrays.binarySearch(consequence,r) < 0){
                                                        sum += r;
                                                }
                                                System.out.println(a+"*"+b+"="+r);
                                                consequence[i++] = r;
                                        }
                                }
                                else{
                                        continue;
                                }
                        }
                        
                }
                System.out.println("去掉重复数字的和为"+sum);
        }
        public static int Record(int[] record,int x){
                int count = 0;
                for(int i = 0;i < record.length;i ++){
                        record[i] = 0;
                }
                int temp = x;
                for(int i = 0;temp != 0;i ++){
                        record[i] = temp % 10;
                        count++;
                        temp /= 10;
                }
                return count;
        }
        public static boolean Pandigital(int[] record,int[] judge,int count){
                boolean flag = true;
        top:for(int i = 0;i < count;i ++){
                        for(int j = 0;j < record.length;j ++){
                                if(judge[i] == record[j]){
                                        flag = false;
                                        break top;
                                }
                        }
                }
                return flag;
        }
        public static boolean Repeat(int[] a,int count){
                boolean flag = false;
                for(int i = 0;i < count-1;i ++){
                        for(int j = i+1;j < count;j ++){
                                if(a[i] == a [j] && !flag){
                                        flag = true;
                                        break;
                                }
                        }
                }
                for(int i = 0;i < count;i ++){
                        if(a[i] == 0){
                                flag = true;
                        }
                }
                return flag;
        }
}

4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
去掉重复数字的和为45228

王小召

6952 = 4 * 1738
7852 = 4 * 1963
5796 = 12 * 483
5346 = 18 * 297
5346 = 27 * 198
4396 = 28 * 157
7254 = 39 * 186
5796 = 42 * 138
7632 = 48 * 159
结果表单：[5346, 5796, 6952, 7852, 4396, 7632, 7254]
代数和:45228
用时：0.2964 秒

import time

def get_pandigital():
    code_list = list(map(str, range(1, 10)))
    target = []
    # x < y
    for x in range(1, 100000):
        for y in range(x, 100000):
            length = len(str(x) + str(y) + str(x * y))
            # eg：100 * 100 = 10000 已经超过9个字母了所以100 * (101,102...)没必要继续了
            if length > 9:
                break
            else:
                if length == 9:
                    l1 = [i for i in (str(x) + str(y) + str(x * y))]
                    l1.sort()
                    if code_list == l1:
                        print("{} = {} * {}".format(x*y, x, y))
                        target.append(x*y)
    return list(set(target)), sum(list(set(target)))

pg_list, summary = get_pandigital()
print("结果表单：{}\n代数和:{}\n用时：{:.4f} 秒".format(pg_list, summary, time.process_time()))

debuggerzh

45228

Process returned 0 (0x0)   execution time : 0.020 s
Press any key to continue.
经分析，算式只可能有一位数*四位数=四位数 或 两位数*三位数=四位数 两种形式
暴力枚举后用set判重

#include<iostream>
#include<set>
#include<cstring>
using namespace std;
int stat[10];

bool parse(int x){
  while(x){
    int t = x % 10;
    if (stat[t]) return false;
    stat[t] = 1;
    x /= 10;
  }
  return true;
}

bool pan(int x,int y,int z){
  memset(stat,0,sizeof(stat));

  if (!parse(x))  return false;
  if (!parse(y))  return false;
  if (!parse(z))  return false;
  if (stat[0])    return false;

  return true;
}

int main(){
  set<int> s;
  int sum = 0;

  for (int a = 2;a < 10;a++){
    for (int b = 1002;b < 10000;b++){
      int c = a * b;
      if (c >= 10000) break;
      if (pan(a,b,c)) s.insert(c);
    }
  }

  for (int a = 12;a < 100;a++){
    for (int b = 102;b < 1000;b++){
      int c = a * b;
      if (c >= 10000) break;
      if (pan(a,b,c)) s.insert(c);
    }
  }

  for (set<int>::iterator it = s.begin();it != s.end();it++){
    sum += *it;
  }
  cout << sum << endl;

  return 0;
}

有马_冬巳

start = time.time()
d = 0
check = []
for a in range(1, 100):
        for b in range(1,10000):
                c = a*b
                check1 = list(str(a)+str(b)+str(c))
                check1.sort()
                check2 = list(set(check1))
                check2.sort()
                if '0' not in str(a) and '0' not in str(b) and '0' not in str(c) and check1 == check2 and len(check2) == 9:
                        print("%d * %d = %d" %(a,b,c))
                        check.append(c)
check = list(set(check))
for each in check:
        d+= each
print("去除重复代数后的代数和为%d" %d)
end = time.time()
print("共用时%f秒" %(end - start))

4 * 1738 = 6952
4 * 1963 = 7852
12 * 483 = 5796
18 * 297 = 5346
27 * 198 = 5346
28 * 157 = 4396
39 * 186 = 7254
42 * 138 = 5796
48 * 159 = 7632
去除重复代数后的代数和为45228
共用时2.755275秒

a1351468657

#include <stdio.h>
#include <string.h>

int check_num(int);
int check_num(int num)
{
        int i, j, a[10] = { 0 };//用于标记数字是否存在

        j = num;
        while (j)
        {
                i = j % 10;
                if (i == 0)
                {
                        return 0;
                }
                if (a[i] == 1)
                {
                        return 0;
                }
                a[i] = 1;
                j /= 10;
        }
        return 1;
}


main()
{
        int i, j, k, sum = 0, e, x = 0, y;
        char str[20];
        int a[10000] = { 0 }; //用于标记数字是否已经加过

        printf("k = ");
        for (i = 1; i < 99; i++)
        {
                for (j = 100; j < 9999; j++)
                {
                        k = i * j;
                        if (k > 10000)
                        {
                                break;
                        }
                        
                        if ((check_num(k) == 0) || (check_num(j) == 0) || (check_num(i) == 0))
                        {
                                continue;
                        }
                        
                        y = k;

                        while (y)
                        {
                                e = y % 10;
                                str[x++] = e + '0';
                                y /= 10;
                        }
                        y = j;
                        while (y)
                        {
                                e = y % 10;
                                str[x++] = e + '0';
                                y /= 10;
                        }
                        y = i;
                        while (y)
                        {
                                e = y % 10;
                                str[x++] = e + '0';
                                y /= 10;
                        }
                        str[x] = '\0';
                        if (strlen(str) < 9)
                        {
                                continue;
                        }
                        y = atoi(str);
                        
                        if (check_num(y))
                        {
                                if (a[k] == 0)
                                {
                                        sum += k;
                                        printf("%d ", k);
                                }
                                a[k] = 1;        
                        }
                        x = 0;
                }
        }
        printf("\nsum = %d\n", sum);
}

答案：
k = 6952 7852 5796 5346 4396 7254 7632
sum = 45228

ft215378

#找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。
from time import *
'''
如果一个n位数使用了1到n中每个数字且只使用了一次，
我们称其为 pandigital。
例如，15234 这个五位数，是1到5pandigital 的。
7254 是一个不寻常的数，
因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了一个1到9的 pandigital 组合。
找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。
'''
#处理字符串
def deal_str(string):
    string_list = []
    for each in string:
        string_list.append(each)
    string_list.sort()
    return string_list

start = time()

numlist = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
res = []
c = 1

for a in range(1, 98):
    for b in range(123, 9876):
        c = a * b
        if deal_str(str(a) + str(b) + str(c)) == numlist:
            res.append([a, b, c])
        
#去除重复项
result = []
for each in res:
    if each[2] not in result:
        result.append(each[2])
    else:
        res.remove(each)
#计算
total = 0
for each in res:
    total += each[2]
end = time()
print(total)
print("用时%.2f秒" % (end - start))

guosl

/*
答案：45228
耗时：0.0250623秒
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int main(void)
{
  char str[12] = "123456789";
  vector<int> v;
  do
  {
    char str1[8], str2[8], str3[8];
    for (int i = 1; i <= 2; ++i)//对第一个乘数的长度进行枚举
    {
      memset(str1, 0, sizeof(str1));
      strncpy(str1, str, i);//得到第一个乘数
      int j = 5 - i;//求得第二个乘数的长度
      memset(str2, 0, sizeof(str2));
      strncpy(str2, str + i, j);//得到第二个乘数
      memset(str3, 0, sizeof(str3));
      strncpy(str3, str + 5, 4);//得到第三个乘数
      int a1 = atoi(str1), a2 = atoi(str2), a3 = atoi(str3);
      if (a1 * a2 == a3)
        v.push_back(a3);//满足要求保存
    }
  } while (next_permutation(str, str + 9));//求出下一个组合
  //去重
  sort(v.begin(), v.end());
  auto itr_end = unique(v.begin(), v.end());
  //求和
  int nSum = 0;
  for (auto itr = v.begin(); itr != itr_end; ++itr)
    nSum += *itr;
  cout << nSum << endl;
  return 0;
}

mathtimes

简单想一想，可能的组合只有这两种：
* x **** = ****
** x *** = ****
剩下的就很简单了
另外，为提升速度，可以使用位运算而不是字符串来存储各个位。
代码：

use std::collections::HashSet;
fn bits(x: usize) -> u32 {
    let mut x = x;
    let mut ans = 0;
    while x != 0 && x % 10 != 0 {
        ans ^= 1 << (x % 10 - 1);
        x /= 10;
    }
    ans
}
fn main() {
    let mut v = HashSet::new();
    for i in 1..=9 {
        for j in 1..=9999 {
            if i * j > 9999 {
                break;
            }
            if bits(i) + bits(j) + bits(i * j) == 0b111111111 {
                v.insert(i * j);
                println!("{} * {} = {}", i, j, i * j)
            }
        }
    }
    for i in 1..=99 {
        for j in 1..=999 {
            if i * j > 9999 {
                break;
            }
            if bits(i) + bits(j) + bits(i * j) == 0b111111111 {
                v.insert(i * j);
                println!("{} * {} = {}", i, j, i * j)
            }
        }
    }
    println!("{}\n{}", v.len(), v.iter().sum::<usize>());
}

输出：

$ time ./main
4 * 1738 = 6952
4 * 1963 = 7852
12 * 483 = 5796
18 * 297 = 5346
27 * 198 = 5346
28 * 157 = 4396
39 * 186 = 7254
42 * 138 = 5796
48 * 159 = 7632
7
45228

real        0m0.002s
user        0m0.002s
sys        0m0.000s