# 工学1号馆

home

## Project Euler 43–Sub-string divisibility

Wu Yudong    August 21, 2018     欧拉计划   638

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这十个数字排列而成；但除此之外，它还有一个有趣的性质：子串的可整除性。

• d2d3d4=406能被2整除
• d3d4d5=063能被3整除
• d4d5d6=635能被5整除
• d5d6d7=357能被7整除
• d6d7d8=572能被11整除
• d7d8d9=728能被13整除
• d8d9d10=289能被17整除

// 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