专栏文章

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

CCARLJOSEPHLEE
B4185题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq49i6b
此快照首次捕获于
2025/12/03 22:42
3 个月前
此快照最后确认于
2025/12/03 22:42
3 个月前
查看原文

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

本题思路

发现 nn 的范围是 1e61e6，所以尝试寻找 O(n)O(n) 的解法。下面分别分析被 44 整除和被 55 整除。
  • 被 55 整除的数，充要条件是个位数为 00 或 55，因为 1010 被 55 整除，所以只需考虑个位数。
  • 被 44 整除的数，首先肯定要是偶数，对于末尾是 0,4,80, 4, 8 的，前面那个数必须要是偶数；对于末尾是 2,62, 6 的，前面那个数必须要是奇数。另一种做法是直接检查最后两位是否能被 44 整除。因为 100100 被 44 整除，所以只需考虑最后两位。

AC 代码如下

PYTHON
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)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...