C - Aladdin and the Flying Carpet 有多少种长方形满足面积为a（<=10^12），且最短边>=b；长方形边长为整数，且一定不可以是正方形。

/**

题目：C - Aladdin and the Flying Carpet

链接：https://vjudge.net/contest/154246#problem/C

题意：有多少种长方形满足面积为a，且最短边>=b；长方形边长为整数，且一定不可以是正方形。

思路：求出a的素因子以及每个素因子的个数，然后搜索所有满足条件的方法数。

其实可以求出所有<b的方法数，用总的减去它，可以更快，不过更麻烦。

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e6+;

ll prime[maxn];

int z;

vector<ll>v;

int num[];

int cous;

ll a, b;

void init()

{

    memset(prime, , sizeof prime);

    for(int i = ; i < maxn; i++){

        if(prime[i]==){

            for(int j = i+i; j < maxn; j+=i){

                prime[j] = ;

            }

        }

    }

    z = ;

    for(int i = ; i < maxn; i++){

        if(prime[i]==){

            prime[z++] = i;

        }

    }

  ///  cout<<"prime number = "<<z<<endl; 78000ge

}

ll ans;

void solve(int h,ll value)

{

    if(h==){

        if(value>=b&&a/value>=b&&value*value!=a) ans++;

        return;

    }

    for(int i = ; i <= num[h-]; i++){

        if(i>){

            value*=v[h-];

        }

        solve(h-,value);

    }

}

int main()

{

    init();

    int T, cas=;

    cin>>T;

    while(T--)

    {

        int cnt = ;

        scanf("%lld%lld",&a,&b);

        v.clear();

        ll n = a;

        cous = ;

        memset(num, , sizeof num);

        for(int i = ; i < z&&prime[i]*prime[i]<=n; i++){

            if(n%prime[i]==){

                v.push_back(prime[i]);

                while(n%prime[i]==){

                    n/=prime[i];

                    num[cous]++;

                }

                cous++;

            }

        }

        if(n>){

            v.push_back(n);

            num[cous++] = ;

        }

        ans = ;

        solve(cous,);

        printf("Case %d: %lld\n",cas++,ans/);

    }

    return ;

}