hdu_5750_Dertouzos(线性筛)

题意：

给你一个n，一个d,问你比n小的数中有多少个数的最大的因子为d，比如6有因子1 2 3 最大的为3

题解：

当时比赛做这题的时候没考虑常数的优化，过了初测，然后FST了，卧槽。。。

这题仔细观察就可以发现我们只需要找一个数s，s*d比n小，且s不大于d的最小的质因数，这样才能使s*d这个数的最大的因子为d。然后我们就用线性筛先筛出2W的素数，其实应该筛到33333的，不过我测试了数据2W也能过，然后就扫一遍就行了

 1 #include<cstdio>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 
 4 int primes[30000],tot=0,N=20000;
 5 bool vis[20001];
 6 void Euler(){
 7     F(i,2,N){
 8         if(!vis[i])primes[++tot]=i;
 9         F(j,1,tot){
10             if(i*primes[j]>N)break;
11             vis[i*primes[j]]=1;
12             if(i%primes[j]==0)break;
13         }
14     }
15 }
16 int main(){
17     Euler();
18     int t,n,d;
19     scanf("%d",&t);
20     while(t--)
21     {
22         scanf("%d%d",&n,&d);
23         int mi=-1,tp=(n-1)/d,ans=0;
24         for(int i=1;i<tot;i++)
25         {
26             if(primes[i]>tp)break;
27             ans++;
28             if(d%primes[i]==0)break;//如果d是当前素数的倍数，那么下一个素数肯定比这个素数大，所以直接退出
29         }
30         printf("%d
",ans);
31     }
32     return 0;
33 }

View Code