1872: 倍数子串(timestr)-2024-小学组/初中组
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:9
Solved:2
Description
Jimmy 对数字有着异于常人的热爱。有一天,他随便写出来一个数字——04320,然后开始对着这个数字写写画画。他发现,从这个数字中随便选出连续的一段(Jimmy 把这个称为连续子串),有可能是 4 的倍数,例如 4,04,32,432 等;也有可能是 5 的倍数,例如 20,320 等。
Jimmy 的老师恰好路过此处,他向正沉迷于自己发现的 Jimmy 提了一个有趣的问题——给定一个指定的数字串,请问有多少连续子串是 4 或者 5 的倍数呢?
老师还特别提醒他:
1. 连续子串的开头可以是 0;
2. 两个连续子串只要是从数字串中的不同位置选出来的,它们就算是不同的;
Jimmy 的老师恰好路过此处,他向正沉迷于自己发现的 Jimmy 提了一个有趣的问题——给定一个指定的数字串,请问有多少连续子串是 4 或者 5 的倍数呢?
老师还特别提醒他:
1. 连续子串的开头可以是 0;
2. 两个连续子串只要是从数字串中的不同位置选出来的,它们就算是不同的;
3. 如果一个连续子串同时是 4 和 5 的倍数,应当只被计算一次哦!
解释:所有满足题意的连续子串分别为:0,04,0432,04320,4,432,4320,32,320,20,0。
其中有两个相同的 0,这是因为它们是从数字串中的不同位置选出来的(一个在开头处,一
个在结尾处)。
Input
一行一个数字串,长度为 n。
Output
一行一个整数,表示所有的连续子串中,为 4 或者 5 的倍数的数量。
Sample Input Copy
04320
Sample Output Copy
11