Responsive image

问题 G: DH的小循环

问题 G: DH的小循环

时间限制: 2 Sec  内存限制: 256 MB
提交: 0  解决: 23
[提交][状态][讨论版][命题人:]

题目描述

DH为了出题和出数据，他的脑子快麻了。因此，他也想让你开动一下脑筋。
给你一个数组a，其中有n个正整数，还有一种操作(可执行无限次)：
令b=ai%10,ai=b+ai(1≤i≤n)。
DH有q次询问，每次询问包含两个整数l,r。
他想问你，在区间[l,r]中，经过一定次数的操作后，有多少个数其末尾(最后一位)会出现0。

输入描述

第一行包含一个整数n,表示数组a中元素的个数，1≤n≤1e5。

第二行包含n个正整数ai，代表数组的元素,1≤ai≤1e9
第三行包含一个正整数q，表示DH询问的次数。(1≤q≤1e5)。
接下来q行，每行包含两个整数l,r,表示DH每次询问的区间范围(1≤l≤r≤n)

输出描述

输出满足条件的数的个数

样例输入

3
13 50 84
2
1 2
2 3

样例输出

1
1

提示

13,84无论经过多少次操作，两个数的末尾(最后一位)永远不会出现0。

50无需操作，其末尾(最后一位)就是0.所以：

[1,2]中的个数为0+1=1

[2,3]中的个数为1+0=1

[提交][状态]
ACM算法攻关部