UVA725 UVALive5362 Division【暴力＋進制】

Write a program that finds and displays all pairs of 5-digit numbers that between them use the digits 0 through 9 once each, such that the first number divided by the second is equal to an integer N, where 2 ≤ N ≤ 79. That is,

where each letter represents a different digit. The first digit of one of the numerals is allowed to be zero.

Input

Each line of the input file consists of a valid integer N. An input of zero is to terminate the program.

Output

Your program have to display ALL qualifying pairs of numerals, sorted by increasing numerator (and, of course, denominator).

  Your output should be in the following general form:

    xxxxx / xxxxx = N

    xxxxx / xxxxx = N

.

.

In case there are no pairs of numerals satisfying the condition, you must write ‘There are no solutions for N.’. Separate the output for two different values of N by a blank line.

Sample Input

61

62

Sample Output

There are no solutions for 61.

79546 / 01283 = 62

94736 / 01528 = 62

Regionals 1990 >> North America - East Central NA

問題連結：UVA725 UVALive5362 Division。

題意簡述：

　　輸入正整數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("\n");
        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\n", abcde, i, n);
                count++;
            }
        }
        if(count == 0)
            printf("There are no solutions for %d.\n", n);
    }

    return 0;
}