问题 C: 3.优美数对(pair)

问题 C: 3.优美数对(pair)

题目描述

  赵琳是爱学习的好孩子,虽然暑假出来探险,玩的很开心,但是她还是没有忘记自己的暑假作业。她把暑假作业也随身带在身上,暑假作业里有很多有趣的问题。例如,有一个由n 个数组成的数组,a[1]到 a[n],需要找出有多少个不同的数对(i,j),满足 a[i]<=a[j],并且恰好存在 k 个 y,使得 a[i]<=y<=a[j],y 必须要被 x 整除。
赵琳觉得这个问题实在太难了,只能用计算机解决。于是她请求强子哥(光头强)帮他解决,可怜的光头强只能屁颠屁颠的去研究程序和算法了。在绞尽脑子之后,他终于做出来了,那你呢?
注意,这里 i 和 j 可以相等。

输入

输入第一行是 3 个整数 n,x,k,n 表示数组中元素的个数,x 和 k 的含义见题目描述。
接下来一行有 n 个正整数,表示 n 个数。

输出

输出只有一行一个非负整数,表示有多少对(i,j)可以满足上面的条件。

样例输入输出

输入#1 复制
4 2 1
1 3 5 7
输出#1 复制
3
输入#2 复制
4 2 0
5 3 1 7
输出#2 复制
4
输入#3 复制
5 3 1
3 3 3 3 3
输出#3 复制
25

提示

【样例 1解释
数对(1,2),(2,3),(3,4)都满足条件。

【样例 2解释】 
数对(1,1),(2,2),(3,3),(4,4)都满足条件。

【样例 3 解释
任意两个数的数对都满足条件。

【数据范围约定】
共计有 20 个测试点。
对于 40%的数据,保证 1<=n<=100,1<=a[i]<=10000,1<=x<=100,0<=k<=100。
对于 70%的数据,保证 1<=n<=1000,1<=a[i]<=1000000,1<=x<=1000,0<=k<=1000。
对于 100%的数据,保证 1<=n<=100000,1<=x<=1000000000,0<=k<=1000000000,1<=a[i]<=1000000000。

序号 标题 作者 发表时间 费用 订购数 操作