一个计数问题——求散列函数碰撞次数

题目来源：NOI导刊
题目大意：某人设计了一个hash函数hash(x,y) = x * y + x + y,把平面上某个点(x,y)(x,y均为非负整数)映射到一个非负整数。现在输入H，要求你给出符合hash(x,y)=h的点的个数。
输入数据：第一行为测试数据个数T，后有T行H。
输出数据：T行，每一行为H对应的点的个数。
数据范围：0
解法一：
把函数变形为y=(h - x)/(x + 1)，然后对[1,h]这个范围内的x逐个测试(h-x) mod (x+1)是否为0。若为0，则ans++。
一个优化：容易知道hash(x,y) = hash(y,x)，据此可以把时间优化到一半。
这个算法整体时间上限是O(MaxT * MaxH)，只能通过3/10的测试点。

解法二：
把函数变形为H+1 = x * y + x + y + 1；因式分解得H+1 = (x + 1) * (y + 1)。
于是，原问题就转化成求H+1能表示成几对正整数相乘了。
故，把H+1质因数分解，然后用乘法原理计算即可。
由于H最大只有100,000,000，因此只要用筛法预处理[1,10000]内的质数就足够了。
需要注意的是，质因数分解后还可能剩下一个大于10000的质数，它的指数一定是1，故把答案×2即可。
解法二的时间复杂度近似T * sqrt(MaxH)，可以通过所有数据。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXP 20000

long totp = 0,p[10000];
int idx[10000];  //指数

void init_prime()   //普通筛法求素数
{
   static _Bool pb[MAXP];
   pb[1] = pb[0] = 1;
   long i,j;
   for(i = 2;i < MAXP;i ++)
       if(pb[i] == 0)
       {
           p[totp ++] = i;
           for(j = i + i;j < MAXP;j += i)
               pb[j] = 1;
       }
}

inline void solve(long x)
{
   x ++;
   long ans = 1;
   memset(idx,0,sizeof(idx));
   long i;
   for(i = 0;i < totp;i ++)
   {
       if(x == 1)    break;
       while(x % p[i] == 0)
       {
           idx[i] ++;
           x /= p[i];
       }
       ans *= idx[i] + 1;
   }
   if(x != 1)    ans *= 2;   //剩余一个大的质因数
   printf("%ld\n",ans);
}

int main()
{
   init_prime();
   freopen("hash.in","r",stdin);
   freopen("hash.out","w",stdout);
   int T;
   long x;
   scanf("%d\n",&T);
   while(T --)
   {
       scanf("%ld",&x);
       solve(x);
   }
   fclose(stdout);
   return 0;
}