UVa 10093 - An Easy Problem!

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址
找出最小的 N ，使得某整數 R 在 N 進位時，可被 N-1 整除。

Solution

若 N - 1 可以將某數 每個位數的總和 整除，則此數在 N 進位時可被 N - 1 整除。

估計是跟同餘定理有關，剛好上學期才修了離散數學也有教到同餘。
有查到這個 解釋，但沒找到很詳細的說明，大概是我餵狗技能沒點滿，如果有錯或是更好的說明還請讓我知道!
這裡先試著解釋看看:

首先假設某數 $X$ 有 $n$ 個位數，每個位數的總和為 $k$ 的倍數，而 $X$ 為 $B$ 進位，且 $B = k + 1$

$$\begin{aligned} &X = a_1a_2a_3 \ldots a_n = a_1 \times B^{(n-1)} + a_2 \times {B^{(n-2)}} + a_3 \times B^{(n-3)} + \cdots + a_n \times {B^0} \\\\ &a_1 + a_2 + a_3 + \cdots + a_n \equiv 0\ (mod\ k) \end{aligned}$$

接著試著將它變成 $X$ ，我們可以發現:

$$\begin{aligned} &a_1 \times k \sum_{i=0}^{n-2} {B^i} + a_2 \times k \sum_{i=0}^{n-3} {B^i} + \cdots + a_{n-1} \times k \sum_{i=0}^{0} {B^i} \equiv 0 \ (mod\ k)\\\\ &a_1 + a_2 + a_3 + \cdots + a_n \equiv 0\ (mod\ k) \end{aligned}$$

第一個式子理所當然是 $k$ 的倍數，畢竟每項都乘上 $k$ 了，而根據 同餘的基本性質 把它們相加後可以得到:
($B = k + 1$)

$X \equiv a_1 \times B^{(n-1)} + a_2 \times {B^{(n-2)}} + a_3 \times B^{(n-3)} + \cdots + a_n \times {B^0} \equiv 0 \ (mod\ k)$

結論: 當 $B = k + 1$ ，且每個位數的總和為 $k$ 的倍數，則 $X$ 在 $B$ 進位時可以被 $k$ 整除。

舉例來說，如果今天是 4 個位數($n = 4$)，且為 10 進位，$k = 9$:

$$\begin{aligned} &X = a_1a_2a_3a_4 = a_1 \times 10^{3} + a_2 \times {10^{2}} + a_3 \times 10^{1} + a_4 \times {10^0}\\\\ &a_1 + a_2 + a_3 + a_4 \equiv 0 \ (mod\ k) \end{aligned}$$

接著相加下面兩式後:
$$\begin{aligned} &a_1 \times 999 + a_2 \times 99 + a_3 \times 9 \equiv 0 \ (mod\ k)\\\\ &a_1 + a_2 + a_3 + a_4 \equiv 0\ (mod\ k) \end{aligned}$$

可以得到 $X$:

$
X \equiv a_1 \times 10^{3} + a_2 \times {10^{2}} + a_3 \times 10^{1} + a_4 \equiv 0 \ (mod\ k)
$

不同的進位制亦如此，但須注意相加時的進位等等不同處。
(以上大概是不嚴謹的證明就是了…)

Code

UVa 10093UVa 10093 - An Easy Problem!

#include<cstdio>
#include<cstring>

inline int findBase(char *str, int& sum);//找出數字每一位中最大的(待會的初始基底不可小於它)，並相加每一位數
int main()
{
    char str[10001];

    while (gets(str))
    {
        int sum;
        int max = findBase(str, sum) , i;

        for (i = max; i < 62; i++)
            if (!(sum%i))
            {
            printf("%d\n", i + 1);
            break;
            }

        if (i == 62)
            puts("such number is impossible!");
    }

    return 0;
}
int findBase(char *str, int& sum)
{
    sum = 0;
    int i, max = 1, len = strlen(str), temp;
    for (i = 0; i < len; i++)
    {
        if (str[i] >= '0'&&str[i] <= '9')
        {
            temp = str[i] - '0';
            if (max < temp)
                max = temp;
            sum += temp;
        }
        else if (str[i] >= 'A'&&str[i] <= 'Z')
        {
            temp = str[i] - 'A' + 10;
            if (max < temp)
                max = temp;
            sum += temp;
        }
        else if (str[i] >= 'a'&&str[i] <= 'z')
        {
            temp = str[i] - 'a' + 36;
            if (max < temp)
                max = temp;
            sum += temp;
        }
    }

    return max;
}