题目大意: 质数序列是指这个序列中任意两个数的和均为质数. 先给出一个序列 ${a_{n}}$, 从中取出元素构成最长质数序列, 问其长度并输出序列. 若长度相同则求和最大的序列. 保证答案唯一.
-----------------
小小的数学题.
1. 偶数 + 偶数不是质数, 奇数 + 奇数不是质数. 但某些偶数 + 奇数 ($1$) 是质数. 所以这个序列中 $1$ 是个很关键的因素.
我们进行分类讨论:
1. 若序列中 $1$ 的个数大于 $2$
长度为所有 $1$ 的个数.
所有 $1$ 再加一个偶数.(此偶数 +$1$ 后为质数)
2. 若序列中 $1$ 的个数等于 $2$
两个 $1$.
两个 $1$ 加一个偶数.
偶数 + 奇数.
3. 若序列中 $1$ 的个数小于 $2$
偶数 + 奇数.
质数需要线性筛预处理.
代码:
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- bool vis[30000010];
- int n,p[1000005],c,a[100005],m,t,s,b;
- signed main()
- {
- scanf("%d",&n);
- for (int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- m=max(m,a[i]);
- if (a[i]==1) c++;
- }
- for (int i=2;i<=m;i++)
- {
- if (!vis[i]) p[++t]=i;
- for (int j=1;j<=t&&i*p[j]<=m;++j)
- {
- vis[i*p[j]]=1;
- if (i%p[j]==0) break;
- }
- }
- sort(a+1,a+n+1);
- if (c>1)
- {
- for (int i=n;i>=1;i--)
- {
- if (!vis[a[i]+1])
- {
- printf("%d\n",c+1);
- for (int j=c;j>=1;j--) printf("1");
- printf("%d",a[i]);
- return 0;
- }
- }
- for (int i=1;i<=c;i++) printf("1");
- return 0;
- }
- for (int i=1;i<=n;i++)
- for (int j=1;j<i;j++)
- if (!vis[a[i]+a[j]]&&a[i]+a[j]>a[s]+a[b]) s=i,b=j;
- if (!a&&!b)
- {
- for (int i=n;i>=1;i--)
- if (!vis[a[i]]) {printf("1\n%d",a[i]);return 0;}
- printf("0");
- }
- printf("2\n%d %d",a[b],a[s]);
- return 0;
- }
[JZOJ4725]质数序列 题解(数学)
来源: http://www.bubuko.com/infodetail-3530940.html