【JZOJ3188】找数【数论，数学】

本文主要是介绍【JZOJ3188】找数【数论，数学】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://jzoj.net/senior/#main/show/3188
找出第 $N$ 个最小素因子是 $P$ 的正整数。

思路：

$\color{red}\texttt{sto\ XXY\ orz}$

$\color{blue}\texttt{sto\ XXY\ orz}$

$\color{green}\texttt{sto\ XXY\ orz}$

$\color{white}\texttt{sto\ XXY\ orz（再加一遍XD）}$

重要的事情说三遍。

这道题 $n\leq 10^9$ 。
XXY $d a l a o$ 给出了 $\frac{1}{10}$ 常数的暴力。
然后就过了。
首先特判 $n = 1$ ，显然输出1。
然后特判 $n > 1$ 且 $p^2>10^9$ ，显然输出0。
接下来依次特判 $p = 2, p = 3, p = 5, p = 7, p = 11$ 。最坏情况下 $p = 5$ 是 $\frac{10^9}{2p}$ 的复杂度。
然后剩下的就是 $p > 11$ 的了。枚举 $p$ 的倍数，判断是否成立。
时间复杂度 $O(10^8+$ 某些常数 $)$ 。鉴于JZOJ评测机很好， $416 m s$ 跑过了。

代码：

#include <cstdio>
#define rr register
using namespace std;
typedef long long ll;const int MAXN=1e9;
const int Psum=35000;
int n,p,cnt,k,prime[Psum],v[Psum];
void find(int maxn)
{for (int i=2;i<=maxn;i++){if (!v[i]){v[i]=i;prime[++cnt]=i;}for (int j=1;j<=cnt;j++){if (prime[j]*i>maxn) break;if (prime[j]>v[i]) break;v[i*prime[j]]=prime[j];}}
}int check(int x)
{for (int i=1;i<k;i++)if (!(x%prime[i])) return 0;return 1;
}int main()
{scanf("%d%d",&n,&p);if (n==1){printf("%d",p);return 0;}if (n>1&&(ll)p*(ll)p>MAXN){printf("0");return 0;}if (p==2){if (n*p<=MAXN) printf("%d",n*p);else printf("0");return 0;}if (p==3){ll x=3+(ll)(n-1)*6;if (x<=MAXN) printf("%lld",x);else printf("0");return 0;}if (p==5){for (rr int i=p;i<=MAXN;i+=2*p)if (i%3){n--;if (!n){printf("%d",i);return 0;}}printf("0");return 0;}if (p==7){for (rr int i=p;i<=MAXN;i+=2*p)if (i%3&&i%5){n--;if (!n){printf("%d",i);return 0;}}printf("0");return 0;}if (p==11){for (rr int i=p;i<=MAXN;i+=2*p)if (i%3&&i%5&&i%7){n--;if (!n){printf("%d",i);return 0;}}printf("0");return 0;}find(Psum);for (k=1;k<=cnt;k++)if (prime[k]==p) break;for (rr int i=p;i<=MAXN;i+=2*p)if (check(i)){n--;if (!n){printf("%d",i);return 0;}}printf("0");return 0;
}