解題區/解題區 - UVa

UVa 268 - Double Trouble

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在一個 B 進制數中，找到一個最小的數字 X，使得 2 * X 的結果恰好是 X 循環右移一位的結果 (意即最末位的數字推到首位，其餘往右推一位)。

例如範例給的

1
2
 X = 421052631578947368 
2X = 842105263157894736

末尾的 8 移動到首位，其餘往右推一位。

Sample Input

1
2
3
2
10
35

Sample Output

1
2
3
4
5
6
For base 2 the double-trouble number is
0 1
For base 10 the double-trouble number is
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
For base 35 the double-trouble number is
11 23

Solution

假設末位數字是 M，且 M 的數值一定介於 $0 <= M < B$，最後根據公式推

$$2*(NM) = MN, 0 \le M < B \\ 2(N * B + M) = N + B^{(k-1)} * M \\ N = M * \frac{(B^{(k-1)} - 2)}{(2 * B - 1)}$$

從位數少開始窮舉，再依序從 M 小的開始窮舉，找到可以整除的整數 N 值，做一次小整數的大數乘除法即可，並不會太難。

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
#include <stdio.h>
/* 
2*(NM) = MN, 0 <= M < B
2(N * B + M) = N + B^(k-1) * M
N = M * (B^(k-1) - 2)/(2 * B - 1)
*/
int main() {
    int B;
    while(scanf("%d", &B) == 1) {
        printf("For base %d the double-trouble number is\n", B);
        
        int d, product = 1, M;
        for(int k = 1; k < 1024; k++) {
            int ok = 0;
            for(M = 1; M < B; M++) {
                if((M * (product - 2))%(2 * B - 1) == 0) {
                    ok = 1, d = k;
                    break;
                }
            }
            if(ok)	break;
            product = (product * B)%(2 * B - 1);
        }
        
        int N[1024] = {};
        N[d - 1] = 1;
        for(int i = 0, carry = -2; i <= d; i++) {
            N[i] += carry;
            if(N[i] < 0) {
                N[i] += B, carry = -1;
            } else {
                break;
            }
        }
        
        for(int i = 0; i <= d; i++)
            N[i] *= M;
        for(int i = 0; i <= d; i++)
            N[i+1] += N[i]/B, N[i] %= B;
        for(int i = d, j = 0; i >= 0; i--) {
            j = j * B + N[i];
            N[i] = j / (2 * B - 1), j %= (2 * B - 1);
        }
        for(int i = d-2; i >= 0; i--)
            printf("%d ", N[i]);
        printf("%d \n", M);
    }
    return 0;
}