Aladdin and the Flying Carpet

题目

给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b。一共询问T<=4000次

分析

首先我们把面积进行质因数分解，得
所以其因子个数就是
此题目的就是让选出合法的因子，我们可以发现x*y = N，选x选y都一样，x!=y,所以本题答案就是 res = cnt/2-小于b的因子,因为本题只需要长方形，所以cnt/2，会自动把x*x = N这种情况去掉。

关于为何打一个小于1e6的质数表就够了

因为我们是要用质数表来选质因数分解，假如N中有且仅有一个因子x且大于1e6，他会在质因数分解迭代完之后自身变成x。代码中这句就是考虑了这种情况if(x>1) res*=2;。所以打一个1e6的质数表就够了。

AC代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;

ll T,N,b;
ll P[maxn],tail;
bool vis[maxn];

void init(){
    int len = (int)sqrt(maxn)+1;
    for(int i = 2;i<=len;i++){
        if(!vis[i]){
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
    for(int i =2;i<maxn;i++){
        if(!vis[i]) P[tail++] = i;
    }

}

ll get_div(ll x){
    ll res = 1;
    for(int i = 0;i<tail && P[i]*P[i]<=x;i++){ //因为P[i]是从小到大遍历的，是所以当P[i]*P[i]>x时，此时他就已经没有除自身之外其他质因数了
        if(x%P[i] == 0){
            ll cnt = 0;
            while(x%P[i] == 0){
                cnt++;
                x/=P[i];
            }
            res *= cnt+1;
        }
    }
    if(x>1) res*=2;
    return res;
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld %lld",&N,&b);
        if(b*b>N){
            printf("Case %d: %d\n",++kase,0);
        }else{
            ll cnt = 0;
            for(int i = 1;i<b;i++) if(N%i == 0) cnt++;
            ll res = get_div(N);
            res/=2;
            printf("Case %d: %lld\n",++kase,res-cnt);
        }
    }
    return 0;
}