题目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，然后分段，再依次判断是否符合要求，找到即终止程序。

from itertools import permutations
from math import gcd
digitsR = [str(i) for i in range(10)][::-1]
for p in permutations(digitsR): 
    for i in range(1,9):
        p1 = int(''.join(p[:i]))
        p2 = int(''.join(p[i:]))
        g = gcd(p1,p2)
        if g>1: 
            q1 = p1//g
            q2 = p2//g
            if sorted([d for m in [g,q1,q2] for d in str(m)], reverse=True) == digitsR:
                print (g,q1,q2,''.join(p))
                exit()

27 36508 149 9857164023
[Finished in 0.4s]

guosl

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <omp.h>
using namespace std;

char a[12] = "9876543210";
bool bContinue = true;

long long GCD(long long a, long long b) //求a,b的最大公因数
{
  if (b == 0)
    return a;
  long long t = a % b;
  while (t != 0)
  {
    a = b;
    b = t;
    t = a % b;
  }
  return b;
}

void fillbits(unsigned char *bs, long long k)
{
  while (k > 0)
  {
    ++bs[k % 10];
    k /= 10;
  }
}

bool chk(vector<long long> v)
{
  if (v.size() == 1)
    return false;
  long long nUp;
  if (v.size() == 2)
    nUp = 99;
  else if (v.size() > 2)
    nUp = 9;
  long long d = v[0];
  for (int i = 1; i < (int)v.size(); ++i)
    d = GCD(d, v[i]);
  d = min(d, nUp);
  for (int i = 2; i <= d; ++i)
  {
    if ((d % i) == 0)
    {
      unsigned char bs[10];
      memset(bs, 0, sizeof(bs));
      fillbits(bs, i);
      for (int j = 0; j < (int)v.size(); ++j)
        fillbits(bs, v[j] / i);
      bool bSuccess = true;
      for (int j = 0; j < 10; ++j)
      {
        if (bs[j] != 1)
        {
          bSuccess = false;
          break;
        }
      }
      if (bSuccess)
        return true;
    }
  }
  return false;
}

bool dfs(vector<long long> v, int k, char *b)
{
  long long x = 0;
  x = atoll(b + k);
  vector<long long> v1 = v;
  v1.push_back(x);
  if (chk(v1))
    return true;
  v1.pop_back();
  x = 0;
  for (int i = k; i < 9; ++i)
  {
    x = 10 * x + int(b[i] - '0');
    v1.push_back(x);
    if (dfs(v1, i + 1, b))
      return true;
    v1.pop_back();
  }
  return false;
}

int main(void)
{
  long long nMax = 0;
#pragma omp parallel shared(a,bContinue) reduction(max:nMax)
  do
  {
    char a1[12];
#pragma omp critical
    {
      memcpy(a1, a, sizeof(a));
      bContinue = prev_permutation(a, a + 10);
    }
    long long x = 0;
    for (int i = 0; i < 9; ++i)
    {
      vector<long long> v;
      x = 10 * x + int(a1[i] - '0');
      v.push_back(x);
      if (dfs(v, i + 1, a1))
      {
        nMax = max(nMax, atoll(a1));
#pragma omp critical
        bContinue = false;
        break;
      }
    }
  }
  while (bContinue);
  cout << nMax << endl;
  return 0;
}