Input
Input starts with an integer T (≤ 4000), denoting the number of test cases.
Each case starts with a line containing two integers: ab(1 ≤ b ≤ a ≤ 1012) 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(<=4000)組資料,求面積是a且邊長均不小于b的矩形個數
思路:直接枚舉b至sqrt(a)的約數分數會逾時,然而先求出總的約數個數/2(成對出現)再減去小于b的所有約數即可(說明b是總體偏小的)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+1000;
bool vis[MAXN];
ll prime[MAXN];
int main()
{
int cnt=0;
for(int i=2;i*i<MAXN;i++)
if(!vis[i])
for(int j=i*i;j<MAXN;j+=i) vis[j]=1;
for(int i=2;i<MAXN;i++)
if(!vis[i]) prime[cnt++]=i;
int T;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
int ans=0;
ll s,lim;
cin>>s>>lim;
ll tmp=s;
if(s>lim*lim)
{
ans=1;
for(int i=0;prime[i]*prime[i]<=s;i++)
{
if(s%prime[i]) continue;
int tmp=0;
while(s%prime[i]==0)
{
tmp++;
s/=prime[i];
}
ans*=(tmp+1);
}
if(s>1) ans*=2;
ans>>=1;
for(int i=1;i<lim;i++) if(tmp%i==0) ans--;
}
cout<<"Case "<<cas<<": "<<ans<<endl;
}
return 0;
}