根据第一个定理,先求出 正因数的个数,再除以二 就是类型数,因为题目说了不为正方形。
要求小于b,则从 1 到 b-1 枚举a的约数,每次找到就少一种类型
当 b>= sqrt(a)时,ans = 0
//LightOJ 1341 - Aladdin and the Flying Carpet
//算数基本定理
#include <bits/stdc++.h>
#define ll long long
#define LL long long
using namespace std;
const int maxn = 1001000;
ll prime[maxn];
void get_prime(){
memset(prime,0,sizeof(prime));
for(int i=2;i<maxn;i++){
if(!prime[i])prime[++prime[0]] = i;
for(int j=1;j<=prime[0]&&prime[j]*i<maxn;j++){
prime[prime[j]*i] = 1;
if(i%prime[j]==0)break;
}
}
}
ll getfact(ll x){
ll ans = 1,tmp = x;
ll j = 1;
while(j<prime[0]&&prime[j]<=tmp){
if(tmp%prime[j]==0){
ll cnt = 0;
while(tmp%prime[j]==0)tmp/=prime[j],cnt++;
ans*=(1+cnt);
}
j++;
}
if(tmp>1)ans*=2;
return ans;
}
int main()
{
get_prime();
int t,cnt=1;
ll a,b,c;
scanf("%d",&t);
while(t--){
scanf("%lld %lld",&a,&b);
if(b>=sqrt(a)){
printf("Case %d: 0\n",cnt++);
continue;
}
c = getfact(a)/2;
for(ll i=1;i<b;i++){
if(a%i==0)
c--;
}
printf("Case %d: %lld\n",cnt++,c);
}
return 0;
}