BestCoder Round #84-白红宇

BestCoder Round #84

阅读量：5066 次

发布时间：2019-06-12

本文共 2049 字，大约阅读时间需要 6 分钟。

1004

思路:求最小质因子，质数个数

官方题解

随便推导下, 令

mp(d),⌊(n−1)/d⌋}.

当 $阈值设置到10^6∼10^7都可以过.$

1 // #pragma comment(linker, "/STACK:102c000000,102c000000") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 // #include 
                  
                   16 using namespace std;17 #define clc(a,b) memset(a,b,sizeof(a))18 #define inf 0x3f3f3f3f19 #define lson l,mid,rt<<120 #define rson mid+1,r,rt<<1|121 const int N = 2e5+10;22 const int M = 1e6+10;23 const int MOD = 1e9+7;24 #define LL long long25 #define mi() (l+r)>>126 double const pi = acos(-1);27 const double eps = 1e-8;28 void fre() {29 freopen("in.txt","r",stdin);30 }31 // inline int r() {32 // int x=0,f=1;char ch=getchar();33 // while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}34 // while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;35 // }36 37 bool np[M];38 int pri[M],g[M];39 int cnt;40 void init(){41 for(int i = 2; i < M; ++i) {42 if(!np[i]) {43 pri[cnt++] = i;44 g[i] = i;45 }46 for(int j = 0; j < cnt && i * pri[j] < M; ++j) {47 np[i*pri[j]] = 1;48 g[i*pri[j]] = pri[j];49 if(i % pri[j] == 0) break;50 }51 }52 }53 54 int calc(int x){55 int ans= upper_bound(pri, pri + cnt, x) - pri;56 return ans;57 }58 int main(){59 // fre();60 init();61 int T;62 scanf("%d",&T);63 while(T--){64 int n,d;65 scanf("%d%d",&n,&d);66 n--;67 if(n<=2*d){68 printf("0\n");69 continue;70 }71 int ans=0;72 if(d>=M){73 int t=(n)/d;74 int f=-1;75 for(int i=0;pri[i]<=t;i++){76 if(d%pri[i]==0){77 f=pri[i];78 break;79 }80 }81 if(f==-1) ans=calc(t);82 else ans=calc(f);83 }84 else{85 int f=min(g[d],(n)/d);86 ans=calc(f);87 }88 printf("%d\n",ans);89 }90 return 0;91 }