AGC 022 B - GCD Sequence

題面在這里！

?

??? 鍛煉腦子的小構造題。。。

??? 一開始被 a[]<=30000 且 序列 gcd = 1所困擾，但是發現這并沒有什么，因為我接下來發現了一種總是能構造出 序列和是6的倍數的方案。

??? 首先如果 n==3 的話輸出樣例，因為只有這種情況沒法用我的方法構造。

?

??? 否則，考慮兩個集合，第一個集合 A 代表<=30000的所有偶數，顯然 |A| = 15000；

??? 第二個集合 B 代表 <=30000的所有非偶數的3的倍數，顯然 |B| = 5000。

??

??? 神奇的發現 |A| + |B|? = n可以取的最大值，那么這種方案能否構造成功呢？

?

??? 設 i 為在B中取的元素個數， j 為在A中取的元素的個數，那么i和j需要滿足（假設我們在每個集合都是從小到大取）:

??????? 1. i+j = n；

??????? 2. i<=5000 && i是偶數;

??????? 3. j<=15000 && j%3不等于1;

?

??? 隨便證一證都可以發現只要 n>3 那么一定有解(不放心的話你甚至可以打表)

?

#include<bits/stdc++.h>
#define ll long long
using namespace std;bool v[30005];
int n,a[20005],t;int main(){scanf("%d",&n);if(n==3){ puts("2 5 63"); return 0;}for(int i=2;i<n;i+=2) if((n-i)<=15000&&i<=5000&&(n-i)%3!=1){for(int j=2,c=1;j<=30000&&c+i<=n;j+=2,c++) printf("%d ",j);for(int j=3,c=1;j<=30000&&c<=i;j+=3) if(j&1) printf("%d ",j),c++;break;}return 0;
}

?