自守数（生成法，Python）

一个n位的非负整数a是自守数当且仅当其平方的后n位是a，即

又知x是自守数，那么x的后n位是自守数（由x对 取模易证），那么，如果x的后n位不是自守数，我们就不用考虑x。于是，我们可以从个位开始向前生成一系列自守数。
设p是一个n位的自守数，现在要从p的前面添加一位（或广义地，若干位）构成新的自守数 ，那么

从而要求 必须是整数。
对 无需考虑 ，如此只需要考虑后几项：由于 是整数，变形得

此即求自守数问题需要求解的同余式。
注意到除自守数0、1以外，自守数个位只能取5或6：一位自守数只有0、1、5、6；末尾n个0的数如果不是0，平方就会得到2n个0，故这样的0要求有无限多个，矛盾；个位是1、十位是k的数平方后十位是 ，只有k=0符合，向前仍然同理，故要求前面的0有无限多个，矛盾。 时 ， 时 ，可以直接看出解，不用解同余方程的通用办法。
这样我们就可以从5、从6分别开始向前推导，每次循环出一个数字。

def automorphic_number_sequence_from_start(num_start, upper_count=None, upper_limit=None):
    if num_start ** 2 % 10 != num_start:
        return []
    if upper_count is not None and upper_count == 1:
        return [num_start]
    current_number = num_start
    nonzero_part = num_start ** 2 // 10
    result = [num_start]
    _base = 1
    _cnt = 1
    while True:
        '''
        # 通用方法
        next_digits = solve_single_mod(2 * num_start - 1, -nonzero_part, 10)
        if not next_digits:
            continue
        # 其他进制下，如果不只一解，还要BFS
        next_digit = next_digits[0]
        '''
        next_digit = right_nonzero % 10 if num_start == 5 else ((10 - right_nonzero % 10) % 10 if num_start == 6 else 0)
        nonzero_part = next_digit ** 2 * _base + (next_digit * (2 * current_number - 1) + nonzero_part) // 10
        if next_digit != 0:
            current_number += next_digit * _base * 10
            if upper_limit is None or current_number <= upper_limit:
                result.append(current_number)
                _cnt += 1
                if upper_count is not None and _cnt >= upper_count:
                    break
            else:
                break
        _base *= 10

    return result


def automorphic_number_sequence(upper_limit):
    if upper_limit < 0:
        return []
    if upper_limit == 0:
        return [0]
    if upper_limit == 1:
        return [0, 1]
    _result = [0, 1] + automorphic_number_sequence_from_start(5, upper_limit=upper_limit) \
           + automorphic_number_sequence_from_start(6, upper_limit=upper_limit)
    _result.sort()
    return _result

期待更高效的不用大数的解法。