[AGC022B] GCD Sequence 做题记录
神仙构造题。
因为 \(\gcd(a_1,a_2,\dots,a_n) =1\)，我们只需要让任意两个数互质即可。不妨在第一、第二项放入 \(2,3\)。
因为 \(\gcd(a,b-a)=\gcd(a,b)\)，所以我们不妨使得 \(30000 \mid \sum_{i=1}^{n} a_i\)，在第三项放入 \(29995\)。
随后我们向数组中连续填写两个和为 \(30000\) 的数，只需要第一个数为 \(2,3,5\) 其中之一的倍数即可。
这样每 \(6\) 个数至少有 \(4\) 个数可以填，所以方案合法。
如果 \(n\) 是偶数再在数组最末端填写一个 \(30000\)。
代码
int n;
signed main() {
in1(n);
int cnt=3;
cout<<"2 3 29995 ";
if(n%2==0) cnt++,cout<<"30000 ";
For(i,6,30000) {
if(cnt<n&&(!(i%2)||!(i%3)||!(i%5)))
cout<<i<<' '<<30000-i<<' ',cnt+=2;
}
}