题目

Problem 571. Super Pandigital Numbers

A positive number is pandigital in base b if it contains all digits from 0 to b - 1 at least once when written in base b.

A n-super-pandigital number is a number that is simultaneously pandigital in all bases from 2 to n inclusively.
For example 978 = 11110100102 = 11000203 = 331024 = 124035 is the smallest 5-super-pandigital number.
Similarly, 1093265784 is the smallest 10-super-pandigital number.
The sum of the 10 smallest 10-super-pandigital numbers is 20319792309.

What is the sum of the 10 smallest 12-super-pandigital numbers?

分析

190AB5634780212 =
4A9827315865011 =
1565970130425810 =
614013746568529 =
3437016735757028 =
32042426655642147 =
531455445500212026 =
40230320320132140135 =
32033200323232332330024

解答

``````#include <stdio.h>

const int max = 12, limit = 10;

int next_perm(char s[])
{ // return: 1:success, 0:fail
int i = max - 1; while (s[i] >= s[i+1]) i--;
if (i == 0) return 0;
int j = max; while (s[i] >= s[j]) j--;
char t = s[i]; s[i] = s[j]; s[j] = t;
for (int a = i+1, b = max; a < b; a++, b--)
t = s[a], s[a] = s[b], s[b] = t;
return 1;
}

long to_decimal(const char s[])
{
long z = 0;
for (int i = 1; i <= max; i++) z = s[i] + z * max;
return z;
}

int is_pandigital(long z, int base)
{
int a = 0;
for (long t; z > 0; z = t) a |= 1 << (z - (t = z / base) * base);
return ++a == 1 << base;
}

int is_super_pandigital(long z)
{
for (int i = max - 1; i >= 5; i--) if (!is_pandigital(z, i)) return 0;
return 1;
}

int main(void)
{
static char a[max + 1]; a[1] = 1; long sum = 0;
for (int i = 3; i <= max; i++) a[i] = i - 1;
for (int n = 0; n < limit; ) {
long z = to_decimal(a);
if (is_super_pandigital(z)) n++, sum += z;
if (!next_perm(a)) break;
}
printf("%ld\n", sum);
return 0;
}
``````

• next_perm 函数按顺序生成下个排列。
• to_decimal 函数把 12 进制数（排列）转换为 10 进制数。
• is_pandigital 函数检查整数 z 是否为 base 进制全能数。
• is_super_pandigital 函数检查整数 z 是否为超级全能数。
• main 函数调用以上函数完成工作。

按顺序生成所有排列

《计算机程序设计艺术·卷4A：组合算法（一）（英文版）》，第 7.2.1.2 节，第 319 页：