计算总位数能被10整除的回文数

Question

如何在0.5秒内从L到R

(1 <= L <= R <= 10^12)

统计有多少个总位数能被10整除的回文数？ 我的想法：生成回文数然后计数。但它是 TLE。 这是我的代码：

def circle_num(x):
    t = 0
    for digit in str(x):
        t += int(digit)
    if t % 10 == 0:
        return True
    else:
        return False
def palinstr_evendig(half):
    return half + half[::-1]
def palinstr_odddig(h):
    return h + (h[::-1])[1:]
def num_palin_circle_num_1to(t, k):
    r = 0; j = 1
    while not int(palinstr_odddig(str(j))) > k:
        a = int(palinstr_evendig(str(j)))
        if (not a > k) and (not a < t) and (circle_num(a)):
            r += 1
        b = int(palinstr_odddig(str(j)))
        if (not b > k) and (not b < t) and (circle_num(b)):
            r += 1
        j += 1
    return r
s = input()
l, r = map(int, s.split())
print(num_palin_circle_num_1to(l, r))

我没有任何想法可以实施。 Python 语言

有人可以帮助我吗？非常感谢。

Answer 1

我假设你正在计算回文数 L ≤ x < R. If R is inclusive, just replace R with R + 1 below.

假设我们有一个函数 f(N)，它可以计算符合您的标准的回文数，使得 0 ≤ x < N. Then we'd just need to calculate F(R) - F(L). [Or f(R + 1) - f(L) is R is inclusive].

那么让我们看看偶回文和奇回文。

• ABCDEEEDCBA 是一个偶数回文。无论 ABCD 是什么，E 都有两个值，使得 A+B+C+D+E 是 5 的倍数。
• ABCDEDCBA 是一个奇怪的回文。无论 ABCD 是什么，E 都恰好有一个值（而且是偶数！），使得 E + 2(A + B + C + D) 是 10 的倍数。

假设我们想要找到 f(314159)。

• 有 1 个长度为 1 (0) 的回文
• 有 1 个长度为 2 (55) 的回文
• 有 9 个长度为 3 的回文。（ABA，其中 1 ≤ A ≤ 9）
• 有 18 = 9 x 2 个长度为 4 的回文。（ABBA，其中 1 ≤ A ≤ 9）
• 有 90 个长度为 5 的回文。（ABCBA, 10 ≤ AB ≤ 99）
• 在 100,000 ≤ x 范围内 < 310,000, the palindromes are of the form ABCCBA, where (10 ≤ AB ≤ 30) and C can have one of two values. So there are 21 x 2 of them.
• 对于最后一位数字，你必须单独查看它们。 311113、312213 和 313313 不是 10 的倍数。 314413 既不是十的倍数，又太大了。

因此，您可以在与 n 中的位数成线性关系的时间内计算 f(n)。

---

实现这一点并不难。我假设您正在尝试计算 f(N)，其中 N 是一个 n 位数字。 N < 100 is trivial (is 0 < N? is 55 < N?), so I'm going to assume n≥3.

的情况

有多少个长度为 m 的 10 回文，其中 1 ≤ m < n?

• 米=1：1
• 米=2：1
• m 奇数且 m > 2：9 * 10 ** ((m - 3) // 2)
• m 偶数且 m > 2: 9 * 2 * 10 ** ((m - 4) // 2

有多少个长度为 n 且小于 N 的 10 回文？ 对于长度n。假设如果 n 为奇数，则 N 为 AB...DED...BA；如果 n 为偶数，则 N 为 AB...DEED...BA。

• 对于每个值 10...0 ≤ ab...d < AB...D, there are 2 palindromes if n is even and 1 palindrome if n is odd. That's a subtraction and maybe a multiplication.
• 最后，对于 AB...D，如果 n 为偶数，则 E 有 2 个可能值；如果 n 为奇数，则 E 有 1 个可能值。您必须检查这两个值以查看它们是否确实如此 < N.

这大约有二十行代码。