Light OJ Aladdin and the Flying Carpet(概数个数)

Light OJ Aladdin and the Flying Carpet(约数个数)

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 ≤ 10¹²) 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

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;
}

Light OJ Aladdin and the Flying Carpet(概数个数)

相关推荐