Aladdin and the Flying Carpet--唯一分解定律

It’s said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the first mystery.

Aladdin was about to enter to a magical cave, led by the evil sorcerer who disguised himself as Aladdin’s uncle, found a strange magical flying carpet at the entrance. There were some strange creatures guarding the entrance of the cave. Aladdin could run, but he knew that there was a high chance of getting caught. So, he decided to use the magical flying carpet. The carpet was rectangular shaped, but not square shaped. Aladdin took the carpet and with the help of it he passed the entrance.

Now you are given the area of the carpet and the length of the minimum possible side of the carpet, your task is to find how many types of carpets are possible. For example, the area of the carpet 12, and the minimum possible side of the carpet is 2, then there can be two types of carpets and their sides are: {2, 6} and {3, 4}.
Input

Input starts with an integer T (≤ 4000), denoting the number of test cases.

Each case starts with a line containing two integers: a b (1 ≤ b ≤ a ≤ 1e12) where a denotes the area of the carpet and b denotes the minimum possible side of the carpet.
Output

For each case, print the case number and the number of possible carpets.
Sample Input

2
10 2
12 2

Sample Output

Case 1: 1
Case 2: 2

题意：t组数据，每组数据a b两个数字，让你找x,y,使得x*y=a,并且x>=b&&y>=b，问你这样的x，y有多少对，(x,y)和(y,x)视为一对。

题解：根据唯一分解定律，能构成数字a的所有x,y的对数为(1+a1)(1+a2)(1+a3)…(1+an),ai为构成数字a的质数的指数，比如样例12,分解为12=223，所以构成12的对数为ans=(1+2)(1+1)=6,分别是：112，26，34，43，62，121，因为题目要求(x,y)和(y,x)是一对，题目也说明了不会有x=y的情况出现，所以答案直接ans/2,又要求x和y都小于等于b，这里又该如何处理呢？考虑b的数据范围，因为b<=a<=1e12,实际上b最大的数据范围是b<=1e6，因为a最大为1e12，如果b大于1e6，那么bb>a，绝对不可能找到x和y,使得x>=b,y>=b，xy=a，所以针对所有b*b>a的情况，对数ans直接为0,所以b的值在1e6范围内，那么通过分解定律求出数字a的所有对数，再一次遍历把x<b的所有情况减去就得到答案了。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[2000100];
vector<int>prime;
//素数筛，由题解分析可知质因数最大为1e6
void init()
{
	prime.clear();
	for(int i=2;i<=1e6+100;i++)
	{
		if(vis[i]==false)
		{
		//把质数装入动态数组
			prime.push_back(i);
			for(int j=2;j*i<=1e6+100;j++)
			vis[i*j]=true;
		}
	}
	vis[1]=true;
}
int main()
{
	int t,cas=0;
	ll a,b;
	init();
//    freopen("data.txt","r",stdin);// 按顺序读入（仅此一行）
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld",&a,&b);
		//如果b*b大于a直接为0
		if(a<b*b)
		{
			printf("Case %d: %lld\n",++cas,0);
			continue;
		}
		ll ans=1;
		ll t=a;
		//开始找质数的指数
		for(int  i=0;i<prime.size();i++)
		{
			int indx=0;
			if(a%prime[i]==0)
			{
				while(a%prime[i]==0)
				{
					indx++;
					a/=prime[i];
				}
				//依次乘质数的指数得到所有对数
				ans*=(1+indx);
			}
			if(a<=1)break;
		}
		//这里很重要，因为如果数字a被完全分解最后a肯定为1，如果不为1说明在1-1e6内没有找到被处理后的数字a的质因数，那么最后被处理的a肯定自身为一个质数，质数的话指数就为1，所以ans*=(1+1)->ans*=2;
		if(a>1)
		ans*=2;
		ans/=2;
		//开始减去不符合要求的
		for(ll i=b-1;i>=1;i--)
		if(t%i==0)
		ans--;
		printf("Case %d: %lld\n",++cas,ans);
	}
	return 0;	
} 
/*
2
10 2
12 2
*/