工学1号馆

home

Project Euler 43–Sub-string divisibility

Wu Yudong    August 21, 2018     欧拉计划   614   

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

No comments yet.
To verify that you are human, please fill in "七"(required)