题目170： 求最大的可以由乘积相连得到的0-9的pandigital数字

欧拉计划

Find the largest 0 to 9 pandigital that can be formed by concatenating products

Take the number 6 and multiply it by each of 1273 and 9854:

        6 × 1273 = 7638
        6 × 9854 = 59124

By concatenating these products we get the 1 to 9 pandigital 763859124. We will call 763859124 the "concatenated product of 6 and (1273,9854)". Notice too, that the concatenation of the input numbers, 612739854, is also 1 to 9 pandigital.

The same can be done for 0 to 9 pandigital numbers.

What is the largest 0 to 9 pandigital 10-digit concatenated product of an integer with two or more other integers, such that the concatenation of the input numbers is also a 0 to 9 pandigital 10-digit number?

题目：

用数字 6 分别乘以 1273 和 9854，得到：

          6 × 1273 = 7638
          6 × 9854 = 59124

将结果连结起来，我们可以得到 1-9 的 pandigital 数字，763859124。我们把 763859124 叫做“6 和 (1273,9854）的连结乘积”。同样要注意到，将输入数字相连接得到的 612739854，也是 1-9 的 pandigital 数字。

对 0-9 的 pandigital 数字，同样的规则也成立。

按照以上过程，将一个整数与两个或更多的其它整数分别相乘，将积相连后得到一个数字 N，N 是 10 位的 0-9 pandigital 数字，同时，输入的这几个数字本身相连，也必须是 10 位的 0-9 pandigital 数字。

现在请问，满足上述条件的 N 的最大值是多少？

jerryxjr1220

先倒序生成所有pandigital，然后分段，再依次判断是否符合要求，找到即终止程序。

1. from itertools import permutations
   
2. from math import gcd
   
3. digitsR = [str(i) for i in range(10)][::-1]
   
4. for p in permutations(digitsR):
   
5.     for i in range(1,9):
   
6.         p1 = int(''.join(p[:i]))
   
7.         p2 = int(''.join(p[i:]))
   
8.         g = gcd(p1,p2)
   
9.         if g>1:
   
10.             q1 = p1//g
    
11.             q2 = p2//g
    
12.             if sorted([d for m in [g,q1,q2] for d in str(m)], reverse=True) == digitsR:
    
13.                 print (g,q1,q2,''.join(p))
    
14.                 exit()

复制代码

27 36508 149 9857164023
[Finished in 0.4s]

guosl

思路同上，但上面的代码只把原数分成了两个部分，我们现在用递归进行完全分解。
答案：9857164023（耗时不到1秒）

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. #include <cstring>
   
5. #include <cmath>
   
6. #include <omp.h>
   
7. using namespace std;
   
8. 
   
9. char a[12] = "9876543210";
   
10. bool bContinue = true;
    
11. 
    
12. long long GCD(long long a, long long b) //求a,b的最大公因数
    
13. {
    
14.   if (b == 0)
    
15.     return a;
    
16.   long long t = a % b;
    
17.   while (t != 0)
    
18.   {
    
19.     a = b;
    
20.     b = t;
    
21.     t = a % b;
    
22.   }
    
23.   return b;
    
24. }
    
25. 
    
26. void fillbits(unsigned char *bs, long long k)
    
27. {
    
28.   while (k > 0)
    
29.   {
    
30.     ++bs[k % 10];
    
31.     k /= 10;
    
32.   }
    
33. }
    
34. 
    
35. bool chk(vector<long long> v)
    
36. {
    
37.   if (v.size() == 1)
    
38.     return false;
    
39.   long long nUp;
    
40.   if (v.size() == 2)
    
41.     nUp = 99;
    
42.   else if (v.size() > 2)
    
43.     nUp = 9;
    
44.   long long d = v[0];
    
45.   for (int i = 1; i < (int)v.size(); ++i)
    
46.     d = GCD(d, v[i]);
    
47.   d = min(d, nUp);
    
48.   for (int i = 2; i <= d; ++i)
    
49.   {
    
50.     if ((d % i) == 0)
    
51.     {
    
52.       unsigned char bs[10];
    
53.       memset(bs, 0, sizeof(bs));
    
54.       fillbits(bs, i);
    
55.       for (int j = 0; j < (int)v.size(); ++j)
    
56.         fillbits(bs, v[j] / i);
    
57.       bool bSuccess = true;
    
58.       for (int j = 0; j < 10; ++j)
    
59.       {
    
60.         if (bs[j] != 1)
    
61.         {
    
62.           bSuccess = false;
    
63.           break;
    
64.         }
    
65.       }
    
66.       if (bSuccess)
    
67.         return true;
    
68.     }
    
69.   }
    
70.   return false;
    
71. }
    
72. 
    
73. bool dfs(vector<long long> v, int k, char *b)
    
74. {
    
75.   long long x = 0;
    
76.   x = atoll(b + k);
    
77.   vector<long long> v1 = v;
    
78.   v1.push_back(x);
    
79.   if (chk(v1))
    
80.     return true;
    
81.   v1.pop_back();
    
82.   x = 0;
    
83.   for (int i = k; i < 9; ++i)
    
84.   {
    
85.     x = 10 * x + int(b[i] - '0');
    
86.     v1.push_back(x);
    
87.     if (dfs(v1, i + 1, b))
    
88.       return true;
    
89.     v1.pop_back();
    
90.   }
    
91.   return false;
    
92. }
    
93. 
    
94. int main(void)
    
95. {
    
96.   long long nMax = 0;
    
97. #pragma omp parallel shared(a,bContinue) reduction(max:nMax)
    
98.   do
    
99.   {
    
100.     char a1[12];
     
101. #pragma omp critical
     
102.     {
     
103.       memcpy(a1, a, sizeof(a));
     
104.       bContinue = prev_permutation(a, a + 10);
     
105.     }
     
106.     long long x = 0;
     
107.     for (int i = 0; i < 9; ++i)
     
108.     {
     
109.       vector<long long> v;
     
110.       x = 10 * x + int(a1[i] - '0');
     
111.       v.push_back(x);
     
112.       if (dfs(v, i + 1, a1))
     
113.       {
     
114.         nMax = max(nMax, atoll(a1));
     
115. #pragma omp critical
     
116.         bContinue = false;
     
117.         break;
     
118.       }
     
119.     }
     
120.   }
     
121.   while (bContinue);
     
122.   cout << nMax << endl;
     
123.   return 0;
     
124. }
     

复制代码