CF45G Prime Problem 构造+数论

时间：2024-12-17 18:35:57

正解:构造+数论

解题报告:

传送门!

maya这题好神仙啊我jio得,,,反正我当初听的时候是没有太懂的,,,

首先这题你要知道一些必要的数学姿势

比如哥德巴赫猜想巴拉巴拉的

然后直接讲题趴QAQ

首先看到说,分成质数之后,不难想到哥德巴赫猜想(,,,什么鬼辣我连哥德巴赫猜想的内容都不清楚哪里不难想到了QAQ

(哥德巴赫猜想:任一大于2的偶数可分为不同俩质数之和)

然后对这n个数的和:sum=n*(n+1)/2分类讨论

1)sum为质数 欧克分成一组就成了!

2)sum为非2偶数 利用哥德巴赫猜想分成俩质数之和凑出来就成了!

3)sum为奇合数,sum-2是质数 显然变成2和质数就好

4)sum为奇合数,sum-2也是奇合数 找出一个奇质数x,显然sum-x后成为情况2(其实情况34可以匹配成一种后QwQ

没了,好妙鸭

放下代码就结束辣!

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define ll int

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

const ll N=+;

ll n,as[N],sum;

inline ll read()

{

    rg ll x=;rg bool y=;rg char ch=getchar();

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

inline bool chck(ll x)

{

    for(rg ll i=;i*i<=x;++i)if(x%i==)return ;

    return ;

}

int main()

{

    n=read();sum=n*(n+)/;

    if(chck(sum)){rp(i,,n)printf("1 ");return ;}

    if(sum&)

    {

        if(chck(sum-)){printf("1 2 ");rp(i,,n)printf("1 ");return ;}

        as[]=;sum-=;

        rp(i,,n)if(chck(i) && chck(sum-i)){as[i]=;break;}

        rp(i,,n)printf("%d ",as[i]+);

        return ;

    }

    rp(i,,n)if(chck(i) && chck(sum-i)){as[i]=;break;}

    rp(i,,n)printf("%d ",as[i]+);

    return ;

}

相关文章