【NOIP模拟赛】hash函数

2014年7月10日1,2140

【问题描述】

明明觉得hash是个好算法,代码短、效率高。某天,他碰到了一个求正方形个数的问题,于是很淡定地枚举对角线,然后用hash判存在,妥妥的搞定,但是提交后却wa了几个点。仔细观察其hash函数为:h=x*y+x+y。为了让明明知道这个函数存在什么问题,对于给出一个h值,请你来告诉他有多少对(x,y)满足上述式子(max(x,y)≤h;h,x,y都为非负整数)?

【输入格式】

多组测试数据,第一行为测试点的个数T,接下来每一行一个整数h,意义如上。

【输出格式】

一共T行,每行一个整数,分别表示有多少组(x,y)满足要其对应的h值。

【数据范围】

对于30%数据,h≤20,000,T≤1000;

对于l00%数据,h≤100,000,000,T≤10000。

【输入样例】

3

1

3

4

【输出样例】

2

3

2

【样例解释】

(1,0),(0,1)

(0,3),(1,1),(3,0)

(4,0),(0,4)

题解

h=x+y+xy

h+1=(x+1)(y+1)

于是只要求出h+1的因数个数即可