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!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#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;
}