题目43：找出所有具有异常子串整除性的pandigital数之和

永恒的蓝色梦想

手动 Permutation
C++ 3ms

#include<iostream>
#include<array>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    array<bool, 10>free;
    array<unsigned char, 10>d;
    free.fill(true);


    for (d[0] = 1; d[0] ^ 10; d[0]++) {
        free[d[0]] = false;

        for (d[1] = 0; d[1] ^ 10; d[1]++) {
            if (free[d[1]]) {
                free[d[1]] = false;

                for (d[2] = 0; d[2] ^ 10; d[2]++) {
                    if (free[d[2]]) {
                        free[d[2]] = false;

                        for (d[3] = 0; d[3] ^ 10; d[3] += 2) {
                            if (free[d[3]]) {
                                free[d[3]] = false;

                                for (d[4] = 3 - (d[2] + d[3]) % 3; d[4] < 10; d[4] += 3) {
                                    if (free[d[4]]) {
                                        free[d[4]] = false;

                                        for (d[5] = 0; d[5] ^ 10; d[5] += 5) {
                                            if (free[d[5]]) {
                                                free[d[5]] = false;

                                                for (d[6] = 0; d[6] ^ 10; d[6]++) {
                                                    if (free[d[6]] && !((d[4] * 100 + d[5] * 10 + d[6]) % 7)) {
                                                        free[d[6]] = false;

                                                        for (d[7] = 0; d[7] ^ 10; d[7]++) {
                                                            if (free[d[7]] && !((d[5] * 100 + d[6] * 10 + d[7]) % 11)) {
                                                                free[d[7]] = false;

                                                                for (d[8] = 0; d[8] ^ 10; d[8]++) {
                                                                    if (free[d[8]] && !((d[6] * 100 + d[7] * 10 + d[8]) % 13)) {
                                                                        free[d[8]] = false;

                                                                        for (d[9] = 0; d[9] < 10; d[9]++) {
                                                                            if (free[d[9]] && !((d[7] * 100 + d[8] * 10 + d[9]) % 17)) {
                                                                                for (auto i : d) {
                                                                                    cout.put('0' + i);
                                                                                }
                                                                                cout << '\n';
                                                                            }
                                                                        }

                                                                        free[d[8]] = true;
                                                                    }
                                                                }

                                                                free[d[7]] = true;
                                                            }
                                                        }

                                                        free[d[6]] = true;
                                                    }
                                                }

                                                free[d[5]] = true;
                                            }
                                        }

                                        free[d[4]] = true;
                                    }
                                }

                                free[d[3]] = true;
                            }
                        }

                        free[d[2]] = true;
                    }
                }

                free[d[1]] = true;
            }
        }

        free[d[0]] = true;
    }
}

a1351468657

渡风 发表于 2017-6-13 00:14
此代码使用matlab编程
Problem43所用时间为491.9989秒
Problem43的答案为16695334890

matlab跟python很像啊

a1351468657

#include <stdio.h>
#include <math.h>

main()
{
        long long int i, sum = 0;
        int j, k, flag = 1, array[7] = { 2, 3, 5, 7, 11, 13, 17 }, temp[10] = { 0 };
        char str[20], num[10];
        for (int a = 1; a < 10; a++)
        {
                temp[a] = 1;
                str[0] = a + '0';
                for (int b = 0; b < 10; b++)
                {
                        if (temp[b])
                        {
                                continue;
                        }
                        temp[b] = 1;
                        str[1] = b + '0';
                        for (int c = 0; c < 10; c++)
                        {
                                if (temp[c])
                                {
                                        continue;
                                }
                                temp[c] = 1;
                                str[2] = c + '0';
                                for (int d = 0; d < 10; d++)
                                {
                                        if (temp[d])
                                        {
                                                continue;
                                        }
                                        temp[d] = 1;
                                        str[3] = d + '0';
                                        for (int e = 0; e < 10; e++)
                                        {
                                                if (temp[e])
                                                {
                                                        continue;
                                                }
                                                temp[e] = 1;
                                                str[4] = e + '0';
                                                for (int f = 0; f < 10; f++) 
                                                {
                                                        if (temp[f])
                                                        {
                                                                continue;
                                                        }
                                                        temp[f] = 1;
                                                        str[5] = f + '0';
                                                        for (int g = 0; g < 10; g++)
                                                        {
                                                                if (temp[g])
                                                                {
                                                                        continue;
                                                                }
                                                                temp[g] = 1;
                                                                str[6] = g + '0';
                                                                for (int h = 0; h < 10; h++)
                                                                {
                                                                        if (temp[h])
                                                                        {
                                                                                continue;
                                                                        }
                                                                        temp[h] = 1;
                                                                        str[7] = h + '0';
                                                                        for (int m = 0; m < 10; m++)
                                                                        {
                                                                                if (temp[m])
                                                                                {
                                                                                        continue;
                                                                                }
                                                                                temp[m] = 1;
                                                                                str[8] = m + '0';
                                                                                for (int n = 0; n < 10; n++)
                                                                                {

                                                                                        if (temp[n])
                                                                                        {
                                                                                                continue;
                                                                                        }
                                                                                        temp[n] = 1;
                                                                                        str[9] = n + '0';
                                                                                        str[10] = '\0';
                                                                                        for (j = 0; j < 7; j++)
                                                                                        {
                                                                                                num[0] = str[j + 1];
                                                                                                num[1] = str[j + 2];
                                                                                                num[2] = str[j + 3];
                                                                                                num[3] = '\0';

                                                                                                k = atoi(num);
                                                                                                if (k % array[j])
                                                                                                {
                                                                                                        flag = 0;
                                                                                                        break;
                                                                                                }
                                                                                        }

                                                                                        if (flag)
                                                                                        {
                                                                                                i = atof(str);
                                                                                                sum += i;
                                                                                                printf("%lld\n", i);
                                                                                        }
                                                                                        flag = 1;
                                                                                        temp[n] = 0;
                                                                                        
                                                                                }
                                                                                temp[m] = 0;
                                                                        }
                                                                        temp[h] = 0;
                                                                }
                                                                temp[g] = 0;
                                                        }
                                                        temp[f] = 0;
                                                }
                                                temp[e] = 0;
                                        }
                                        temp[d] = 0;
                                }
                                temp[c] = 0;
                        }
                        temp[b] = 0;
                }
                temp[a] = 0;
                
        }
        printf("\n%lld\n", sum);

}

1406357289
1430952867
1460357289
4106357289
4130952867
4160357289

sum = 16695334890

guosl

这个问题我们用OpenMP的平行编程来处理

/*
答案：16695334890
耗时：0.276207秒（单核）
      0.0415891（八核）
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <omp.h>
using namespace std;

const int d[] = { 2,3,5,7,11,13,17 };
//线程里面不能处理的内容太少，否则反而把更多的时间花在线程切换和等待上
const int nSteps = 256;//线程每次处理的数的个数

int main(void)
{
  char str[12] = "0123456789";
  long long nSum = 0;
  volatile bool bContinue = true;
#pragma omp parallel shared(bContinue,str) reduction(+:nSum)
  while (bContinue)
  {
    char str1[12], str2[4];
    int nK = 0;
#pragma omp critical
    {
      //获得当前要处理的数据
      strcpy_s(str1, str);
      for (nK = 0; bContinue && nK < nSteps; ++nK)
        bContinue = next_permutation(str, str + 10);//处理出给其他线程用的值
    }
    for (int j = 0; j < nK; ++j)
    {
      bool bFlag = true;
      for (int i = 0; i < 7; ++i)
      {
        strncpy_s(str2, str1 + (i + 1), 3);
        str2[3] = 0;
        int a = atoi(str2);
        if (a % d[i] != 0)
        {
          bFlag = false;
          break;
        }
      }
      if (bFlag)
      {
        long long k = 0;
        for (int i = 0; i < 10; ++i)
        {
          k *= 10;
          k += int(str1[i] - 48);
        }
        nSum += k;
      }
      next_permutation(str1, str1 + 10);
    }
  }
  cout << nSum << endl;
  return 0;
}

B1tetheDust

import time as t
from itertools import permutations

start = t.perf_counter()


def have_traits(a_tuple):
    list_dn = []
    divisors = [2, 3, 5, 7, 11, 13, 17]
    for n in range(1, 8):
        list_dn.append(int(a_tuple[n] + a_tuple[n + 1] + a_tuple[n + 2]))
    for index in range(7):
        if not (list_dn[index] // divisors[index] == list_dn[index] / divisors[index]):
            return False
    else:
        return True


num_list = list(permutations('0123456789'))
nums = []
for num_tuple in num_list:
    if len(num_tuple) == 10 and have_traits(num_tuple):
        num_str = ''
        for i in range(10):
            num_str += num_tuple[i]
        nums.append(int(num_str))

print(nums)
print(sum(nums))
print("It costs %f s" % (t.perf_counter() - start))

[1406357289, 1430952867, 1460357289, 4106357289, 4130952867, 4160357289]
16695334890
It costs 10.803681 s