Poj在線評測平臺，poj2689Prime Distance

2023-10-21 阅读 34 评论 0

摘要：這題……一開始沒想到后來題意就是求區間素數對最大和最小距離發現必須處理所有素數復雜度要求是O(n)～O(nlgn) Poj在線評測平臺、考慮分開求質數和合數其實就是篩法篩合數最后遍歷一遍找最大最小值即可然后這個方法篩素數到R?就可以了也就是50000（WA是寫

這題……一開始沒想到后來

題意就是求區間素數對最大和最小距離

發現必須處理所有素數

復雜度要求是O(n)～O(nlgn)

Poj在線評測平臺、考慮分開求質數和合數其實就是篩法篩合數

最后遍歷一遍找最大最小值即可

然后這個方法篩素數到R^?就可以了

也就是50000（WA是寫的40000……）

Time cost:55min

poj1741、Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #include<vector>
 7 #define ms(a,b) memset(a,b,sizeof a)
 8 #define rep(i,a,n) for(int i = a;i <= n;i++)
 9 #define per(i,n,a) for(int i = n;i >= a;i--)
10 #define inf 2147483647
11 using namespace std;
12 typedef long long ll;
13 ll read() {
14     ll as = 0,fu = 1;
15     char c = getchar();
16     while(c < '0' || c > '9') {
17         if(c == '-') fu = -1;
18         c = getchar();
19     }
20     while(c >= '0' && c <= '9') {
21         as = as * 10 + c - '0';
22         c = getchar();
23     }
24     return as * fu;
25 }
26 const int N = 100005;
27 //head
28 ll l,r;
29 ll mindiv[N],prime[N];
30 int top;
31 void initprime(int n) {
32     rep(i,2,n) {
33     if(!mindiv[i]) prime[++top] = i;
34     for(int j = 1;j <= top && i * prime[j] <= n;j++) {
35         mindiv[prime[j] * i] = prime[j];
36         if(i % prime[j] == 0) break;
37     }
38     }
39 }
40 
41 int flag[N<<4],tot;
42    
43 int main() {
44     initprime(50000);
45     while(~scanf("%lld%lld",&l,&r)) {
46     tot++;
47     if(l == 1) l++;
48     rep(i,1,top) {
49         if(prime[i] * prime[i] > r) break;
50         rep(j,(l+prime[i]-1)/prime[i],r/prime[i]) 
51         if(j > 1) flag[j * prime[i] - l] = tot;
52     }
53     ll minn = 10000007,maxx = 0;
54     ll minid[2],maxid[2];
55     ll cur = 0,curr = 0;
56     rep(i,l,r) {
57         if(flag[i-l] == tot) continue;
58         cur = curr,curr = i;
59         if(!cur) continue;
60         if(curr - cur < minn) minn = curr - cur,minid[0] = cur,minid[1] = curr;
61         if(curr - cur > maxx) maxx = curr - cur,maxid[0] = cur,maxid[1] = curr;
62     }
63     if(!maxx) puts("There are no adjacent primes.");
64     else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minid[0],minid[1],maxid[0],maxid[1]);
65     }
66     return 0;
67 }