欧拉计划 发表于 2016-9-15 01:01:24

题目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 发表于 2017-9-21 14:46:07

本帖最后由 jerryxjr1220 于 2017-9-21 14:52 编辑

先倒序生成所有pandigital，然后分段，再依次判断是否符合要求，找到即终止程序。
from itertools import permutations
from math import gcd
digitsR = [::-1]
for p in permutations(digitsR):
    for i in range(1,9):
      p1 = int(''.join(p[:i]))
      p2 = int(''.join(p))
      g = gcd(p1,p2)
      if g>1:
            q1 = p1//g
            q2 = p2//g
            if sorted( for d in str(m)], reverse=True) == digitsR:
                print (g,q1,q2,''.join(p))
                exit()
27 36508 149 9857164023

guosl 发表于 2022-10-13 21:06:11

本帖最后由 guosl 于 2022-10-14 21:35 编辑

思路同上，但上面的代码只把原数分成了两个部分，我们现在用递归进行完全分解。
答案：9857164023（耗时不到1秒）
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <omp.h>
using namespace std;

char a = "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;
}
}

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;
for (int i = 1; i < (int)v.size(); ++i)
    d = GCD(d, v);
d = min(d, nUp);
for (int i = 2; i <= d; ++i)
{
    if ((d % i) == 0)
    {
      unsigned char bs;
      memset(bs, 0, sizeof(bs));
      fillbits(bs, i);
      for (int j = 0; j < (int)v.size(); ++j)
      fillbits(bs, v / i);
      bool bSuccess = true;
      for (int j = 0; j < 10; ++j)
      {
      if (bs != 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 - '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;
#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 - '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;
}
页: [1]
查看完整版本: 题目170： 求最大的可以由乘积相连得到的0-9的pandigital数字