题解 | #[NOIP1999]回文数#

思路1:利用十进制做中转
1.将m 和 reverse(m) 转为10进制并求和
2.将sum转回 n 进制, 更新为 m
3.判断是否m是否为回文串

代码如下:

package main

import (
	"fmt"
	"strconv"
)

func reverse(s string) string {
	str := ""
	for _, k := range s {
		str = string(k) + str
	}
	return str
}
func toDecimal(s string, n int) int {
	res, length, cur := 0, len(s), 1
	for i := length - 1; i >= 0; i-- {
		if s[i] <= '9' {
			res += int(s[i]-'0') * cur
		} else if s[i] <= 'Z' {
			res += (int(s[i]-'A') + 10) * cur
		} else {
			res += (int(s[i]-'a') + 10) * cur
		}
		cur *= n
	}
	return res
}
func main() {
	var (
		n int    // 进制数
		m string // 数
	)
	fmt.Scan(&n, &m)
	for i := 1; i <= 30; i++ {
		rm := reverse(m)
		m10, rm10 := toDecimal(m, n), toDecimal(rm, n)
		m = strconv.FormatInt(int64(m10+rm10), n)
		if reverse(m) == m {
			fmt.Printf("STEP=%d", i)
			return
		}
	}
	fmt.Println("Impossible!")
}

思路2:高精度