C - Aladdin and the Flying Carpet （ 唯一分解定理求因子个数 ）

C - 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 ≤ 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

题意： 一个长方形， 给出面积a ， 限制其最短的边长必须大于等于b ， 求有几种组合方式。

思路：根据唯一分解定理，先将a唯一分解，则a的所有正约数的个数为num = (1 + a1) * (1 + a2) *...(1 + ai)，这里的ai是素因子的指数，见唯一分解定理，因为题目说了不会存在c==d的情况（是长方形），因此num要除2，去掉重复情况，然后枚举小于b的a的约数，拿num减掉就可以了

优化1：上面说了要枚举小于b又是a的约数的，那么b是1e12的肯定会超时， 这里需要提前判断 if ( a<b*b ) cout<<"0"<<endl; 意思是如果连长方形的边都是最小边都大于面积的话，一定是0. 这样b的范围就变成1e6了。

优化2：在质因子分解的时候会有一个边界条件，朴素的是 只要 x>0 我就让while继续，直到能除以一个素数就除。 可以优化成如果当前素数的平方大于x就结束，（这样可以从n的复杂度优化成根号n）， 因为我们是从小忘大找素因子， 那么剩下的x一定可以分解成两个素数的乘积，如果连两个当前最小的乘积都无法分解成自然结束了， 这里在结束时需要判断，如果x>1，就是虽然x无法分解成2个数的乘积了； 但是还可以分解成1个数，所以需要注意一下。

 

代码;

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;
typedef long long ll;
int primes[maxn],cnt;
bool isprime[maxn];

void get_prime() // 得到素数表
{
    for ( int i=0; i<=maxn; i++ ) isprime[i]=1;
    cnt = 0;
    isprime[0] = isprime[1] = 0;
    int i;
    for ( i=2; i*i<=maxn; i++ ) {
        if ( isprime[i]==1 ) {
            primes[cnt++] = i;
            for ( int j=i*i; j<=maxn; j+=i ) {
                isprime[j] = 0;
            }
        }
    }
    for ( ;i<=maxn; i+=2 ) {
        if ( isprime[i]==1 ) primes[cnt++] = i;
    }
}


int solve( ll x ) // 返回x的因子个数
{
    int ans = 1;
    for ( int i=0; primes[i]<=sqrt(x)&&i<cnt; i++ ) { // 优化2
        int tot = 0;  // 这个primes[i]<=sqrt(x)必须优化， 如果是x>0直接T飞
        while ( x%primes[i]==0 ) {
            x /= primes[i];
            tot ++;
        }
        ans *= (tot+1);
    }
    if ( x>1 ) ans*=(1+1); // //如果x不能被整分，说明还有一个素数是它的约数，此时tot=1
    return ans;
}

int main()
{
    get_prime();
    ll listt,n,m,ji=1;
    cin >> listt;
    while ( listt-- ) {
        scanf("%lld %lld",&n, &m);
        if ( n<m*m ) {  // 这个条件必须加， 直接把下面m的for循环从1e12 变成了1e6
            printf("Case %lld: 0\n",ji++); // 优化1
        }
        else {
            int ans = solve(n);
            ans /= 2;
            for ( int i=1; i<m; i++ ) {
                if ( n%i==0 ) ans --;
            }
            printf("Case %lld: %lld\n",ji++,ans);
        }
    }

    return 0;
}