题意：给你n，将1-n中的数字分成尽量少的集合，使得每个集合的和都为素数，输出集合数和方案。n<=6000
【jzoj|【GDOI2018模拟7.8】质数 乱搞+哥德巴赫猜想】想了一会儿发现模型可以化简，其实只要先求出总和，然后分分分就可以了。
问题是怎么分。
一开始想了个sb方法，因为我如果线筛求出素数以后，直接硬上背包的话会T
然后就贪心找最大的，每一次拿最大的去填，感觉好像有问题，但是这种方法好像在哪里见过就没有多想直接上了，拍一些数据也居然过了。
然后挂了3个点。
这种思想是在多重背包的二进制拆分，那里能用是因为每一个物品我都能拆成1，所以最优肯定是先填大的然后填小的，这里肯定不行。
所以，我们直接暴力判断sum是否可以由两个素数组成，可以的话就求方案，不可以的话有两种情况：
根据哥德巴赫猜想：任一大于5的整数都可写成三个质数之和，答案如果不是无解肯定是3。
我们先把1-n中最大素数抽出（肯定用得上），然后剩下的两个暴力找（自己随便暴力），如果找不到就-1，找得到就是3。
话说用这种未证明的东西出题真的好吗
（巨丑无比的代码，注意答案=2时找方案应该也是暴力，但是我懒得改了，spj水）
#include
#include
#include
#define fo(i,a,b) for(int i=a;
i<=b;
i++)
#define fd(i,a,b) for(int i=a;
i>=b;
i--)
using namespace std;
const int N=6e3+5;
typedef long long ll;
int a[N*N],tot,b[N];
int vis[N];
bool vis1[N*N];
int n,sum;
inline int find(int x)
{
int l=1,r=tot,ans=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (a[mid]<=x)l=mid+1,ans=mid;
else r=mid-1;
}
return a[ans];
}
inline bool pd(int x)
{
int cnt=0,sum1=sum;
while(1)
{
int p=find(sum1);
//printf("%d %d\n",p,sum1);
if (!p)return 0;
sum1-=p;
cnt++;
if (!sum1)break;
}
if (cnt>x)return 0;
else return 1;
}
inline void prime(int n)
{
fo(i,2,n)
{
if (!vis1[i])a[++tot]=i;
fo(j,1,tot)
{
if(i*a[j]>n)break;
vis1[i*a[j]]=1;
if (i%a[j]==0)break;
}
}
}
int main()
{
scanf("%d",&n);
sum=(1+n)*n/2;
prime(sum);
int l=1,r=n,ans=-1;
while (l<=r)
{
int mid=(l+r)>>1;
if (pd(mid))r=mid-1,ans=mid;
else l=mid+1;
}
if (ans==-1)
{
b[1]=find(n);
sum-=b[1];
int i=1,j=tot;
while(i<=j)
{
if (a[i]+a[j]==sum)
{
sum=0;
b[2]=a[i],b[3]=a[j];
break;
}
if (a[i]+a[j]>sum)j--;
else i++;
}
if (sum)
{
printf("-1\n");
return 0;
}
ans=3;
printf("%d\n",ans);
fo(i,1,ans)
{
fd(j,n,1)
if (!vis[j]&&j<=b[i])
{
vis[j]=i;
b[i]-=j;
if (!b[i])break;
}
}
fo(i,1,n)printf("%d ",vis[i]);
printf("\n");
}
else
if (ans!=-1)
{
printf("%d\n",ans);
fo(i,1,ans)b[i]=find(sum),sum-=b[i];
fo(i,1,ans)
{
fd(j,n,1)
if (!vis[j]&&j<=b[i])
{
vis[j]=i;
b[i]-=j;
if (!b[i])break;
}
}
fo(i,1,n)printf("%d ",vis[i]);
printf("\n");
}
} 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element