Aladdin and the Flying Carpet

题目大意：

给你一个长方形面积和一个最小可能的边长，统计有多少种满足面积相等且边长大于等于最小边长的长方形。

解题思路：

正常的对a开方然后找因子会超时，用唯一分解定理先找出面积a的因子数量，如果b*b>a则答案为0，否则从1-b暴力找一下满足条件的因子，最后减去即可。这个题我用欧拉筛求素数表的时候莫名的超时，百度了一下换成埃式筛居然过了。。。什么鬼啊，欧拉不是最快的线性筛选法吗？给个超时是什么情况。。
TLE代码：

#include<iostream>
#include<cstdio>
#include<fstream>
#include<set>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<list>
#include<queue>
#include<stack>
#include<algorithm>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define meminf(a) memset(a,inf,sizeof(a))
#define MAXN 1000100
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int prime[MAXN];
bool vis[MAXN];
int getprime()
{
  int cnt=0;
  for(int i=2;i<MAXN;i++)
  {
    if(!vis[i])
    {
     prime[cnt++]=i;
     vis[i]=1;
    }
    for(int j=0;j<cnt&&prime[j]*i<MAXN;j++)
    {
      if(i%prime[j]==0)break;
      vis[i*prime[j]]=1;
    }
  }
  return cnt;
}
ll solve(ll n,int len)
{
  int cur=0;
  ll result=1;
  while(n>1&&cur<len)
  {
    int k=0;
    while(n%prime[cur]==0)
    {
      k++;
      n/=prime[cur];
    }
    result*=(k+1);
    cur++;
  }
  if(n!=1)result*=2;
  return result;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
//  freopen("test.txt","r",stdin);
//  freopen("output.txt","w",stdout);
  int len=getprime();
  int t,cas=1;
  cin>>t;
  while(t--)
  {
    ll n,side,result=0;
    cin>>n>>side;
    ll num=solve(n,len);
    ll cnt=0;
    if(side*side>n)result=0;
    else
    {
     for(ll i=1;i<side;i++)
     {
       if(n%i==0)cnt++;
     }
     result=num/2-cnt;
     if(result<0)result=0;
   }
    cout<<"Case "<<cas++<<": "<<result<<endl;
  }
}

AC代码：

#include<iostream>
#include<cstdio>
#include<fstream>
#include<set>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<list>
#include<queue>
#include<stack>
#include<algorithm>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define meminf(a) memset(a,inf,sizeof(a))
#define MAXN 1000100
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int prime[MAXN];
bool vis[MAXN];
ll getprime()//埃氏筛
{
   memset(vis, true, sizeof(vis));
   vis[1] = false;
   for(int i=2;i<MAXN;i++)
   {
     if(vis[i])
     {
        for(int j=i+i;j<MAXN;j+=i)
        {
           vis[j] = false;
        }
     }
   }
   ll top=0;
   for(int i=2;i<=MAXN;i++)
   {
     if(vis[i])
     {
        prime[top++] = i;
     }
   }
   return top;
}
ll solve(ll n,int len)//唯一分解定理
{
  int cur=0;
  ll result=1;
  while(n>1&&cur<len)
  {
    int k=0;
    while(n%prime[cur]==0)
    {
      k++;
      n/=prime[cur];
    }
    result*=(k+1);
    cur++;
  }
  if(n!=1)result*=2;
  return result;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
//  freopen("test.txt","r",stdin);
//  freopen("output.txt","w",stdout);
  int len=getprime();
  int t,cas=1;
  cin>>t;
  while(t--)
  {
    ll n,side,result=0;
    cin>>n>>side;
    ll num=solve(n,len);
    ll cnt=0;
    if(side*side>n)result=0;
    else
    {
     for(ll i=1;i<side;i++)
     {
       if(n%i==0)cnt++;
     }
     result=num/2-cnt;//记住要除2，因为num是因子的数量
     if(result<0)result=0;
   }
     cout<<"Case "<<cas++<<": "<<result<<endl;
  }
}