题解：B4185 [中山市赛 2024] 倍数子串

CARLJOSEPHLEE · 2025-02-28 09:58:38 · 题解

题解：B4185 [中山市赛 2024] 倍数子串

本题思路

发现 n 的范围是 1e6，所以尝试寻找 O(n) 的解法。下面分别分析被 4 整除和被 5 整除。

• 被 5 整除的数，充要条件是个位数为 0 或 5，因为 10 被 5 整除，所以只需考虑个位数。

• 被 4 整除的数，首先肯定要是偶数，对于末尾是 0, 4, 8 的，前面那个数必须要是偶数；对于末尾是 2, 6 的，前面那个数必须要是奇数。另一种做法是直接检查最后两位是否能被 4 整除。因为 100 被 4 整除，所以只需考虑最后两位。

AC 代码如下

from sys import stdin
input = lambda: stdin.readline().rstrip() #这是python的快读

a = input()
n = len(a)
cnt = 0

for i in range(n):
    temp =  int(a[i]) #末尾数
    if temp in [0,5]:
        cnt += i+1
    elif temp in [2,6]:
        try:
            if int(a[i-1])%2 == 1:
                cnt += i
        except:
            pass
    elif temp in [4,8]:
        cnt += 1
        try:
            if int(a[i-1])%2 == 0:
                cnt += i
        except:
            pass
print(cnt)