[C++知识库]Aladdin and the Flying Carpet LightOJ - 1341

题

给一组数字 a，b 。其中，a表示一个长方形的面积，现在想知道有多少种整数的边的组合可以组成面积为a的矩形，而且要求矩形的最短的边不得小于b
注意：不能是正方形

Input

第一行是一个整数 T (≤ 4000) 表示数据的组数 每组数据包含两个整数: a,b(1 ≤ b ≤ a ≤ 1012) 其中 a表示矩形的面积 ，b为最小边.

Output

对每组数据, 输出数据序号及可能的矩形的个数（参考样例）.

Sample Input

2
10 2
12 2

Sample Output

Case 1: 1
Case 2: 2

代码

#include "stdio.h"
#include "math.h"
typedef long long ll;
int a[1000009];
int b[1000000],l=0;
void ppp()
{
	for(int i=2; i<=1000000; i++)
	{
		if(a[i]==0)
		{
			b[l++]=i;
			for(int j=i*2; j<=1000000; j+=i)
				a[j]=1;
		}
	}
}
ll find(ll s)
{
	ll sum=1;
	if(s==1)
		return 1;
	for(int i=0; i<l&&b[i]*b[i]<=s; i++)
	{
		int k=0;
		while(s%b[i]==0)
		{
			k++;
			s/=b[i];
		}
		sum*=(k+1);//因数的个数相乘
	}
	if(s>=2)//s现在为质数
		sum*=2;//相当于sum*=(k+1),k=1;
	return sum/2;//因子配对
}
int main()
{
	int n;
	ppp();
	scanf("%d",&n);
	ll s,side;//面积，边长
	for(int k=1; k<=n; k++)
	{
		scanf("%lld %lld",&s,&side);
		if(side*side>=s)
		{
			printf("Case %d: 0\n",k);
			continue;
		}
		ll sum=find(s);
		for(int i=1; i<side; i++)
			if(s%i==0)
				sum--;
		printf("Case %d: %lld\n",k,sum);
	}
}

解释sum*=(k+1)