Sub-string divisibility
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
- d2d3d4=406 is divisible by 2
- d3d4d5=063 is divisible by 3
- d4d5d6=635 is divisible by 5
- d5d6d7=357 is divisible by 7
- d6d7d8=572 is divisible by 11
- d7d8d9=728 is divisible by 13
- d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
子串的可整除性
1406357289是一个0至9全数字数，因为它由0到9这十个数字排列而成；但除此之外，它还有一个有趣的性质：子串的可整除性。
记d1是它的第一个数字，d2是第二个数字，依此类推，我们注意到：
- d2d3d4=406能被2整除
- d3d4d5=063能被3整除
- d4d5d6=635能被5整除
- d5d6d7=357能被7整除
- d6d7d8=572能被11整除
- d7d8d9=728能被13整除
- d8d9d10=289能被17整除
找出所有满足同样性质的0至9全数字数，并求它们的和。
思路：
利用前面的文章《全排列的生成算法–字典序法》中提供的算法，在生成排列的同时判断是否符合，代码如下：
// Project Euler 43–Sub-string divisibility
// Completed on Tue, 21 Aug 2018, 16:32
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define N 10
int arr[N] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };
int b[8] = { 0, 2, 3, 5, 7, 11, 13, 17 };
//交换list[a],list[b]
void Swap(int list[], int a, int b)
{
int temp = 0;
temp = list[a];
list[a] = list[b];
list[b] = temp;
return;
}
//将list区间[a,n]之间的数据由小到大排序
void Sort(int list[], int a, int n)
{
int temp = 0;
for (int i = 1; i < n - a; ++i) {
for (int j = a + 1; j < n - 1; ++j) {
if (list[j] > list[j + 1]) {
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
return;
}
long long count(int *a, int n)
{
bool flag = true;
int d;
long long ans;
ans = a[0];
for (int i = 1; i <= n - 3; i++) {
d = a[i] * 100 + a[i + 1] * 10 + a[i + 2];
if (d % b[i]) {
flag = false;
ans = 0;
break;
}
}
if (flag) {
for (int i = 1; i < n; i++) {
ans *= 10;
ans += a[i];
}
printf("%lld\n", ans);
}
return ans;
}
//全排列
void Prim(int list[], int n)
{
int num = 1, a = 0, b = 0;
long long sum = 0;
for (int i = n; i > 0; --i) //计算有多少种情况，就循环多少次
num *= i;
while (num--) {
sum += count(list, n);
for (int i = n - 1; i > 0; --i) {//从右往左，找出第一个左边小于右边的数，设为list[a]
if (list[i - 1] < list[i]) {
a = i - 1;
break;
}
}
for (int j = n - 1; j > a; --j) {//从右往左，找出第一个大于list[a]的数，设为list[b]
if (list[j] > list[a]) {
b = j;
break;
}
}
Swap(list, a, b); //交换list[a],list[b]
Sort(list, a, n); //将list[a]后面的数据，由小往大排列
}
printf("sum:%lld\n", sum);
return;
}
int main()
{
int begintime, endtime;
begintime = clock(); //计时开始
Prim(arr, N);
endtime = clock(); //计时结束
printf("Running Time: %dms\n", endtime - begintime);
return 0;
}
1406357289
1430952867
1460357289
4106357289
4130952867
4160357289
sum:16695334890
Running Time: 104ms
Answer:16695334890
Completed on Tue, 21 Aug 2018, 16:32
Comments