LightOJ – 1341 Aladdin and the Flying Carpet

题目链接

因为有4000个case, 直接累计约数的话会超时,每个case的复杂度达10^6.

用算术基本定理的推论,则要先质数打表,不然对每个数进行质因数分解时还要一边求质数,会造成很多不必要的循环(质数之间有很多间隔).

奇怪的是后面剔除宽为1~b的时候,复杂度应该也为10^6,这样却不超时了.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int v[1000005];
int p[1000005];
int k;
void primes(int n){
  for(int i=2;i<=n;++i){
    if(v[i]) continue;
    p[++k]=i;
    for(int j=i;j<=n/i;++j) v[i*j]=1;
  }
}

ll divide(ll n){
    ll res=1;
    for(int i=1;i<=k;++i){
      int t=0;
      if(n<p[i]) break;
      while(n%p[i]==0){
        n/=p[i];
        t++;
      }
      res*=(t+1);
    }
    if(n>1) res*=2;
    return res;
}

int main() {
  int T,kase=0;
  cin>>T;
  primes(1000000);
  while(T--){  
    ll a,b;
    cin>>a>>b;
    ll ans=divide(a)/2;
    if(b>=sqrt(a)) ans=0;
    else{
       for(int i=1;i<b;++i){
         if(a%i==0) ans--;
      }
    }
    printf("Case %d: %lld\n",++kase,ans);

  }
  return 0;
}