求特殊自然数

题意

求一个自然数，使其七进制和九进制表示均为三位，且两种表示的数字顺序恰好相反。

思路

三位九进制数至少为 $9^2$ ，三位七进制数小于 $7^3$ ，只需枚举公共区间。to_base 用反复取余生成低位，再反转得到正常表示；比较 base7 == base9[::-1] 即可。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def to_base(number, base):
    digits = []
    while number:
        digits.append(str(number % base))
        number //= base
    return "".join(reversed(digits))


for number in range(9**2, 7**3):
    base7 = to_base(number, 7)
    base9 = to_base(number, 9)
    if len(base7) == len(base9) == 3 and base7 == base9[::-1]:
        print(number)
        print(base7)
        print(base9)
        break

C++代码

cpp

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#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str_7[100];
char str_9[100];
int tran_to(int n,char a[],int base){
    int i,idx = 0;
    while( n != 0){
        int ret = n % base;
        a[idx++] = ret+'0';
        n = n / base;
    }
    for(i=0;i<idx/2;i++){
        swap(a[i],a[idx-i-1]);
    }
    return idx;
}

bool compare(){
    int i;
    for(i=0;i<3;i++){
        if( str_7[i] != str_9[2-i])
            return 0;
    }
    return 1;
}

int main(){
    int i;
    for(i=248;i<=999;i++){
        memset(str_7,0,sizeof(str_7));
        memset(str_9,0,sizeof(str_9));
        int len_7 = tran_to(i,str_7,7);
        if(len_7 != 3)
            continue;
        int len_9 = tran_to(i,str_9,9);
        if(len_9 != 3)
            continue;
        if( compare()){
            printf("%d\n",i);
            printf("%s\n",str_7);
            printf("%s",str_9);
            break;
        }
    }
    return 0;
}

复杂度

枚举范围固定，时间复杂度和额外空间复杂度均为 $O(1)$ 。

总结

进制转换的基本过程是反复取余；从低位收集后反转即可恢复高位到低位顺序。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结