Solution
其实根本不需要楼上的 \(\mathsf{Pollard\_rho}\) 或 区间筛 算法。
考虑如何暴力计算一个数 \(n\) 的约数:从 \(1\) 到 \(\sqrt n\) 枚举约数即可。
那么我们可以直接给 \(m=b-a=10^4\) 个数开一个桶,从 \(1\) 到 \(\sqrt b\) 枚举约数,在其 \(\left[a,b\right]\) 里的倍数的桶中加上,这样的复杂度为 \(\mathcal O(\dfrac{m}{1}+\dfrac{m}{2}+\dfrac{m}{3}+\cdots+\dfrac{m}{m})=\mathcal O(m\ln m)\),轻松拿到最优解。
Code
代码也很短
#include<stdio.h>
#include<math.h>
int a,b,n,cnt[10005],ans;
int main(){
scanf("%d%d%d",&a,&b,&n);
int sb=sqrt(b),i,j;
for(i=1;i<=sb;++i)for(j=(a%i?a+i-a%i:a);j<=b;j+=i)
cnt[j-a]+=(i*i<j?2:(i*i==j?1:0));
for(i=a;i<=b;++i)ans+=(cnt[i-a]==n);
printf("%d",ans);
return 0;
}