正題

---

題目大意

求第$n$大的最小質(zhì)因數(shù)時$p$的數(shù)。

---

解題思路

首先對于$p=2$和$p=3$時可以直接通過計算得出。
然后不難發(fā)現(xiàn)當$p=5$時我們可以每次增加$10$也就是$O(n)$的十分之一常數(shù)。
之后再往大的我們發(fā)現(xiàn)是$O(\frac{n\ln n}{p})$常數(shù)是二分之一。
然后可以過。

---

$code$

#pragma GCC optimize(2) #include<cstdio> #include<algorithm> #define ll long long using namespace std; const ll inf=1e9; ll n,p,pri[764579],tot; bool v[11000000]; int main() {for(ll i=2;i<=1e7;i++)if(!v[i]){pri[++tot]=i;for(ll j=i;j<=1e7;j+=i)v[j]=1;}scanf("%lld%lld",&n,&p);if(n==1){printf("%d",p);return 0;}n--;if(p==2){if(2*n+2>inf) printf("0");else printf("%lld",2*n+2);}if(p==3){if(n*6+1>inf) printf("0");else printf("%lld",n*6+1);}if(p==5){for(ll i=5*5;i<=inf;i+=10){if(i%3!=0) n--;if(!n){printf("%lld",i);return 0;}}putchar('0');}if(p==7){for(ll i=p*p;i<=inf;i+=14){if(i%3!=0&&i%5!=0) n--;if(!n){printf("%lld",i);return 0;}}putchar('0');}if(p==11){for(ll i=p*p;i<=inf;i+=22){if(i%3!=0&&i%5!=0&&i%7!=0) n--;if(!n){printf("%lld",i);return 0;}}putchar('0');}if(p>11){ll mp=lower_bound(pri+1,pri+1+tot,p)-pri-1;for(ll i=p*p;i<=inf;i+=2*p){bool flag=1;for(ll j=2;j<=mp;j++)if(i%pri[j]==0){flag=0;break;}if(flag)n-=flag;if(!n){printf("%lld",i);return 0;}}putchar('0');} }

總結

以上是生活随笔為你收集整理的jzoj3188-找数【质数筛,数论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。