51nod1184 第N个质数

如题。$n leq 1e9$。
方法零：二分，然后洲阁筛。要魔改一下的洲阁筛。跑得慢。卡卡能过。没意思。
 1 //#include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cstdio>
 5 //#include<map>
 6 #include<math.h>
 7 //#include<time.h>
 8 //#include<complex>
 9 #include<algorithm>
10 using namespace std;
11 
12 #define LL long long
13 LL n,mzz=10000000;
14 #define maxn 640011
15 #define maxm 10000011
16 int prime[maxm/10],sp[maxm],lp; bool notprime[maxm];
17 void pre()
18 {
19     lp=0;
20     for (int i=2;i<=mzz;i++)
21     {
22         if (!notprime[i]) {prime[++lp]=i;}
23         sp[i]=sp[i-1]+!notprime[i];
24         for (int j=1,tmp;j<=lp && 1ll*prime[j]*i<=mzz;j++)
25         {
26             notprime[tmp=i*prime[j]]=1;
27             if (i%prime[j]); else break;
28         }
29     }
30 }
31 
32 LL G(int i,LL j)
33 {
34     if (i==1) return (j+1)>>1;
35     if (j<=prime[i]) return 1;
36     if (j<=mzz && j<=(LL)prime[i]*prime[i]) return sp[j]+1-i;
37     return (G(i-1,j)-G(i-1,j/prime[i]));
38 }
39 
40 LL mg(LL n) {return G(lp,n);}
41 
42 LL calc(LL n)
43 {
44     if (n<=mzz) return sp[n];
45     lp=1; for (;(LL)prime[lp]*prime[lp]<=n;lp++);
46     return mg(n)-1+sp[prime[lp]];
47 }
48 
49 int q;
50 int main()
51 {
52     scanf("%d",&q); pre();
53     LL L=1,R=22801763489;
54     if (q>=900000001) L=20422213579; else R=20422213579;
55     if (q>=925000001) L=21016060633; else R=21016060633;
56     if (q>=950000001) L=21610588367; else R=21610588367;
57     if (q>=970000001) L=22086742277; else R=22086742277;
58     if (q>=985000001) L=22444149523; else R=22444149523;
59     while (L<R)
60     {
61         LL mid=(L+R)>>1,tmp;
62         if ((tmp=calc(mid))>=q) R=mid;
63         else L=mid+1;
64     }
65     printf("%lld
",L);
66     return 0;
67 }
View Code