Problem 471 Magic Numbers

輸入一個 n 值，請你找出所有 s1 / s2 的數，但有唯一條件，就是以上出現的每個數(n 或 s1 或 s2)，每個位數不會重複出現。例如： 1234567890 就符合條件， 1123 就不符合條件。

首先寫一個檢查位數的函式，符合就回傳 1，反之，回傳 0，C 語言程式碼如下：

int check (long long int n)
{
    int repeat[10] = {0};
    for (; n; n /= 10)
    {
        int tmp = n % 10;
        if (repeat[tmp]) return 0;
        repeat[tmp] = 1;
    }
    return 1;
}

接下來只要用一迴圈，初設 s1 = n, s2 = 1，找尋每個 s1 / s2 = n 的數值，在我實驗看來，s2 不會超過 180000。 C 語言程式碼如下：

long long int s1, s2, limit, n;
scanf("%d", &caseNum);

for (i = 0; i < caseNum; i ++)
{
    scanf("%lld", &n);
    limit = 180000;
    if (i != 0) printf("\n");
    for (s2 = 1, s1 = n; s2 < limit; s1 += n, s2 ++)
    {
        if (check(s1) && check(s2))
            printf("%lld / %lld = %lld\n", s1, s2, n);
    }
}

By David.K

p471題目連結
回ACM題庫目錄
回首頁