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

永恒的蓝色梦想

手动 Permutation
C++ 3ms

1. #include<iostream>
   
2. #include<array>
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     using namespace std;
   
8.     ios::sync_with_stdio(false);
   
9. 
   
10.     array<bool, 10>free;
    
11.     array<unsigned char, 10>d;
    
12.     free.fill(true);
    
13. 
    
14. 
    
15.     for (d[0] = 1; d[0] ^ 10; d[0]++) {
    
16.         free[d[0]] = false;
    
17. 
    
18.         for (d[1] = 0; d[1] ^ 10; d[1]++) {
    
19.             if (free[d[1]]) {
    
20.                 free[d[1]] = false;
    
21. 
    
22.                 for (d[2] = 0; d[2] ^ 10; d[2]++) {
    
23.                     if (free[d[2]]) {
    
24.                         free[d[2]] = false;
    
25. 
    
26.                         for (d[3] = 0; d[3] ^ 10; d[3] += 2) {
    
27.                             if (free[d[3]]) {
    
28.                                 free[d[3]] = false;
    
29. 
    
30.                                 for (d[4] = 3 - (d[2] + d[3]) % 3; d[4] < 10; d[4] += 3) {
    
31.                                     if (free[d[4]]) {
    
32.                                         free[d[4]] = false;
    
33. 
    
34.                                         for (d[5] = 0; d[5] ^ 10; d[5] += 5) {
    
35.                                             if (free[d[5]]) {
    
36.                                                 free[d[5]] = false;
    
37. 
    
38.                                                 for (d[6] = 0; d[6] ^ 10; d[6]++) {
    
39.                                                     if (free[d[6]] && !((d[4] * 100 + d[5] * 10 + d[6]) % 7)) {
    
40.                                                         free[d[6]] = false;
    
41. 
    
42.                                                         for (d[7] = 0; d[7] ^ 10; d[7]++) {
    
43.                                                             if (free[d[7]] && !((d[5] * 100 + d[6] * 10 + d[7]) % 11)) {
    
44.                                                                 free[d[7]] = false;
    
45. 
    
46.                                                                 for (d[8] = 0; d[8] ^ 10; d[8]++) {
    
47.                                                                     if (free[d[8]] && !((d[6] * 100 + d[7] * 10 + d[8]) % 13)) {
    
48.                                                                         free[d[8]] = false;
    
49. 
    
50.                                                                         for (d[9] = 0; d[9] < 10; d[9]++) {
    
51.                                                                             if (free[d[9]] && !((d[7] * 100 + d[8] * 10 + d[9]) % 17)) {
    
52.                                                                                 for (auto i : d) {
    
53.                                                                                     cout.put('0' + i);
    
54.                                                                                 }
    
55.                                                                                 cout << '\n';
    
56.                                                                             }
    
57.                                                                         }
    
58. 
    
59.                                                                         free[d[8]] = true;
    
60.                                                                     }
    
61.                                                                 }
    
62. 
    
63.                                                                 free[d[7]] = true;
    
64.                                                             }
    
65.                                                         }
    
66. 
    
67.                                                         free[d[6]] = true;
    
68.                                                     }
    
69.                                                 }
    
70. 
    
71.                                                 free[d[5]] = true;
    
72.                                             }
    
73.                                         }
    
74. 
    
75.                                         free[d[4]] = true;
    
76.                                     }
    
77.                                 }
    
78. 
    
79.                                 free[d[3]] = true;
    
80.                             }
    
81.                         }
    
82. 
    
83.                         free[d[2]] = true;
    
84.                     }
    
85.                 }
    
86. 
    
87.                 free[d[1]] = true;
    
88.             }
    
89.         }
    
90. 
    
91.         free[d[0]] = true;
    
92.     }
    
93. }

复制代码

a1351468657

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

matlab跟python很像啊

a1351468657

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. main()
   
5. {
   
6.         long long int i, sum = 0;
   
7.         int j, k, flag = 1, array[7] = { 2, 3, 5, 7, 11, 13, 17 }, temp[10] = { 0 };
   
8.         char str[20], num[10];
   
9.         for (int a = 1; a < 10; a++)
   
10.         {
    
11.                 temp[a] = 1;
    
12.                 str[0] = a + '0';
    
13.                 for (int b = 0; b < 10; b++)
    
14.                 {
    
15.                         if (temp[b])
    
16.                         {
    
17.                                 continue;
    
18.                         }
    
19.                         temp[b] = 1;
    
20.                         str[1] = b + '0';
    
21.                         for (int c = 0; c < 10; c++)
    
22.                         {
    
23.                                 if (temp[c])
    
24.                                 {
    
25.                                         continue;
    
26.                                 }
    
27.                                 temp[c] = 1;
    
28.                                 str[2] = c + '0';
    
29.                                 for (int d = 0; d < 10; d++)
    
30.                                 {
    
31.                                         if (temp[d])
    
32.                                         {
    
33.                                                 continue;
    
34.                                         }
    
35.                                         temp[d] = 1;
    
36.                                         str[3] = d + '0';
    
37.                                         for (int e = 0; e < 10; e++)
    
38.                                         {
    
39.                                                 if (temp[e])
    
40.                                                 {
    
41.                                                         continue;
    
42.                                                 }
    
43.                                                 temp[e] = 1;
    
44.                                                 str[4] = e + '0';
    
45.                                                 for (int f = 0; f < 10; f++)
    
46.                                                 {
    
47.                                                         if (temp[f])
    
48.                                                         {
    
49.                                                                 continue;
    
50.                                                         }
    
51.                                                         temp[f] = 1;
    
52.                                                         str[5] = f + '0';
    
53.                                                         for (int g = 0; g < 10; g++)
    
54.                                                         {
    
55.                                                                 if (temp[g])
    
56.                                                                 {
    
57.                                                                         continue;
    
58.                                                                 }
    
59.                                                                 temp[g] = 1;
    
60.                                                                 str[6] = g + '0';
    
61.                                                                 for (int h = 0; h < 10; h++)
    
62.                                                                 {
    
63.                                                                         if (temp[h])
    
64.                                                                         {
    
65.                                                                                 continue;
    
66.                                                                         }
    
67.                                                                         temp[h] = 1;
    
68.                                                                         str[7] = h + '0';
    
69.                                                                         for (int m = 0; m < 10; m++)
    
70.                                                                         {
    
71.                                                                                 if (temp[m])
    
72.                                                                                 {
    
73.                                                                                         continue;
    
74.                                                                                 }
    
75.                                                                                 temp[m] = 1;
    
76.                                                                                 str[8] = m + '0';
    
77.                                                                                 for (int n = 0; n < 10; n++)
    
78.                                                                                 {
    
79. 
    
80.                                                                                         if (temp[n])
    
81.                                                                                         {
    
82.                                                                                                 continue;
    
83.                                                                                         }
    
84.                                                                                         temp[n] = 1;
    
85.                                                                                         str[9] = n + '0';
    
86.                                                                                         str[10] = '\0';
    
87.                                                                                         for (j = 0; j < 7; j++)
    
88.                                                                                         {
    
89.                                                                                                 num[0] = str[j + 1];
    
90.                                                                                                 num[1] = str[j + 2];
    
91.                                                                                                 num[2] = str[j + 3];
    
92.                                                                                                 num[3] = '\0';
    
93. 
    
94.                                                                                                 k = atoi(num);
    
95.                                                                                                 if (k % array[j])
    
96.                                                                                                 {
    
97.                                                                                                         flag = 0;
    
98.                                                                                                         break;
    
99.                                                                                                 }
    
100.                                                                                         }
     
101. 
     
102.                                                                                         if (flag)
     
103.                                                                                         {
     
104.                                                                                                 i = atof(str);
     
105.                                                                                                 sum += i;
     
106.                                                                                                 printf("%lld\n", i);
     
107.                                                                                         }
     
108.                                                                                         flag = 1;
     
109.                                                                                         temp[n] = 0;
     
110.                                                                                        
     
111.                                                                                 }
     
112.                                                                                 temp[m] = 0;
     
113.                                                                         }
     
114.                                                                         temp[h] = 0;
     
115.                                                                 }
     
116.                                                                 temp[g] = 0;
     
117.                                                         }
     
118.                                                         temp[f] = 0;
     
119.                                                 }
     
120.                                                 temp[e] = 0;
     
121.                                         }
     
122.                                         temp[d] = 0;
     
123.                                 }
     
124.                                 temp[c] = 0;
     
125.                         }
     
126.                         temp[b] = 0;
     
127.                 }
     
128.                 temp[a] = 0;
     
129.                
     
130.         }
     
131.         printf("\n%lld\n", sum);
     
132. 
     
133. }

复制代码

1406357289
1430952867
1460357289
4106357289
4130952867
4160357289

sum = 16695334890

guosl

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

1. /*
   
2. 答案：16695334890
   
3. 耗时：0.276207秒（单核）
   
4.       0.0415891（八核）
   
5. */
   
6. #include <iostream>
   
7. #include <algorithm>
   
8. #include <cstring>
   
9. #include <omp.h>
   
10. using namespace std;
    
11. 
    
12. const int d[] = { 2,3,5,7,11,13,17 };
    
13. //线程里面不能处理的内容太少，否则反而把更多的时间花在线程切换和等待上
    
14. const int nSteps = 256;//线程每次处理的数的个数
    
15. 
    
16. int main(void)
    
17. {
    
18.   char str[12] = "0123456789";
    
19.   long long nSum = 0;
    
20.   volatile bool bContinue = true;
    
21. #pragma omp parallel shared(bContinue,str) reduction(+:nSum)
    
22.   while (bContinue)
    
23.   {
    
24.     char str1[12], str2[4];
    
25.     int nK = 0;
    
26. #pragma omp critical
    
27.     {
    
28.       //获得当前要处理的数据
    
29.       strcpy_s(str1, str);
    
30.       for (nK = 0; bContinue && nK < nSteps; ++nK)
    
31.         bContinue = next_permutation(str, str + 10);//处理出给其他线程用的值
    
32.     }
    
33.     for (int j = 0; j < nK; ++j)
    
34.     {
    
35.       bool bFlag = true;
    
36.       for (int i = 0; i < 7; ++i)
    
37.       {
    
38.         strncpy_s(str2, str1 + (i + 1), 3);
    
39.         str2[3] = 0;
    
40.         int a = atoi(str2);
    
41.         if (a % d[i] != 0)
    
42.         {
    
43.           bFlag = false;
    
44.           break;
    
45.         }
    
46.       }
    
47.       if (bFlag)
    
48.       {
    
49.         long long k = 0;
    
50.         for (int i = 0; i < 10; ++i)
    
51.         {
    
52.           k *= 10;
    
53.           k += int(str1[i] - 48);
    
54.         }
    
55.         nSum += k;
    
56.       }
    
57.       next_permutation(str1, str1 + 10);
    
58.     }
    
59.   }
    
60.   cout << nSum << endl;
    
61.   return 0;
    
62. }
    

复制代码

B1tetheDust

1. import time as t
   
2. from itertools import permutations
   
3. 
   
4. start = t.perf_counter()
   
5. 
   
6. 
   
7. def have_traits(a_tuple):
   
8.     list_dn = []
   
9.     divisors = [2, 3, 5, 7, 11, 13, 17]
   
10.     for n in range(1, 8):
    
11.         list_dn.append(int(a_tuple[n] + a_tuple[n + 1] + a_tuple[n + 2]))
    
12.     for index in range(7):
    
13.         if not (list_dn[index] // divisors[index] == list_dn[index] / divisors[index]):
    
14.             return False
    
15.     else:
    
16.         return True
    
17. 
    
18. 
    
19. num_list = list(permutations('0123456789'))
    
20. nums = []
    
21. for num_tuple in num_list:
    
22.     if len(num_tuple) == 10 and have_traits(num_tuple):
    
23.         num_str = ''
    
24.         for i in range(10):
    
25.             num_str += num_tuple[i]
    
26.         nums.append(int(num_str))
    
27. 
    
28. print(nums)
    
29. print(sum(nums))
    
30. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

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