因为有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;
}