UVA725 UVALive5362 Division

Regionals 1990 >> North America - East Central NA

这可以说是最快枚举程序，比网上现有的暴力枚举程序要快。

问题链接：UVA725 UVALive5362 Division。基础练习题，用C语言编写程序。

题意简述：输入正整数n，用0~9这10个数字不重复组成两个五位数abcde和fghij，使得abcde/fghij的商为n，按顺序输出所有结果。如果没有找到则输出“There are no solutions for N.”。这里2<=n<=79。

问题分析：没有什么好办法，就暴力枚举吧！不过还是要下点功夫，否则10！的计算量是不可想象的。

1.因为n>=2，且abcde=fghij×n，满足abcde>fghij。若a=0，则fghij的最小值为12345，abcde<fghij，矛盾。所以a≠0。

2.因为a≠0，所以12345<=abcde<=98765，01234<=fghij。

3.因为2≤n，且abcde≤98765，那么fghij = abcde/n，得fghij≤98765/2=49382，所以01234≤fghij≤49382。

4.因为12345≤abcde≤98765，且01234≤fghij≤49382，所以用fghij进行枚举范围比较小。（这是在任意的n的条件下得出的结论）

5.对于给定的n，因为abcde≤98765，那么fghij = abcde/n，得fghij≤98765/n。结论：01234≤fghij≤98765/n。

程序说明：（略）

AC的C语言程序如下：

/* UVA725 UVALive5362 Division */

#include <stdio.h>
#include <memory.h>

#define DIGITNUM 10

int check(int abcde, int fghij)
{
    int used[DIGITNUM], d;

    memset(used, 0, sizeof(used));

    if(fghij < 10000)
        used[0] = 1;

    while(abcde) {
        d = abcde % 10;
        if(used[d])
            return 0;
        used[d] = 1;

        abcde /= 10;
    }

    while(fghij) {
        d = fghij % 10;
        if(used[d])
            return 0;
        used[d] = 1;

        fghij /= 10;
    }

    return 1;
}

int main(void)
{
    int n, abcde, count, caseflag=0, end, i;

    while(scanf("%d", &n) != EOF && n != 0) {
        if(caseflag)
            printf("
");
        caseflag = 1;

        count = 0;
        end = 98765 / n;
        for(i=1234; i<=end; i++) {
            abcde = i * n;
            if(abcde >= 12345 && check(abcde, i)) {
                printf("%05d / %05d = %d
", abcde, i, n);
                count++;
            }
        }
        if(count == 0)
            printf("There are no solutions for %d.
", n);
    }

    return 0;
}