正題

題目鏈接:https://www.luogu.com.cn/problem/CF476D

---

題目大意

求$n$個四元組使得

• 所有四元組內(nèi)沒有重復(fù)的數(shù)。
• 四元組內(nèi)的數(shù)字兩兩之間$gcd$都為$k$。

要求使得最大的數(shù)字最小
$1\le n\le 10000,1\le k\le 100$

---

解題思路

首先$k$是沒有用的因為可以視為互質(zhì)，然后再乘$k$，然后考慮如何構(gòu)造。

考慮每次在原來$n?1$個四元組的基礎(chǔ)上加入四個數(shù)然后重新排列使得合法，首先對于任意$x$都有$x,x+1,x+2$肯定是互質(zhì)的，所以一種比較可能正確的方法是把這三個排到一個二元組，然后再考慮剩下那個排啥，顯然$x+4$不行，那就只能排$x+5$了。

這樣一次占用了六個數(shù)字，可以證明是最優(yōu)的做法但是我不會證/kk。

時間復(fù)雜度：$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll n,k; signed main() {scanf("%lld%lld",&n,&k);printf("%lld\n",(6ll*n-1)*k);for(ll i=1;i<=n;i++)printf("%lld %lld %lld %lld\n",(6ll*i-5ll)*k,(6ll*i-4ll)*k,(6ll*i-3ll)*k,(6ll*i-1ll)*k);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF476D-Dreamoon and Sets【结论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。