「ARC118C」 Coprime Set

题意

给定 \(n\)，构造一个长度为 \(n\) 的数组，满足任意两个数不互质且不相同，所有数的最大公因数为 \(1\)，且每个数最大为 \(10000\)。

分析

这种限制了数的大小，不限制大小和位置关系的构造题有一个套路。

先找出几个最小的满足条件的数，然后找出延申的条件。

对于本题，当 \(n=3\) 时，有一组最简单的答案是 \(6,10,15\)，它们分别是 \(2\times3,2\times 5,3\times5\)。

可以发现这三个数的倍数只要不是另外两个数的倍数都可以加入数组。

所以可以枚举这三个数的倍数，把符合条件的数保留。

总时间复杂度 \(O(n)\)。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
// static char buf[100],*p1=buf,*p2=buf,obuf[100],*p3=obuf;
// #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++
// #define putchar(x) (p3-obuf<100)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
inline void write(ll x){if(!x){putchar(48);putchar(' ');return;}char top=0,s[40];if(x<0)x=-x,putchar(45);while(x)s[top++]=x%10^48,x/=10;while(top--)putchar(s[top]);putchar(' ');}
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
const ll mod=1e9+7,maxn=1e5+5,maxt=505;
ll n;
vector<ll>q;
inline void solve(){
    n=read()-3;
    write(6),write(10),write(15);
    for(ll i=2;i*6<=10000&&q.size()<n;++i){
        q.push_back(i*6);
    }
    for(ll i=2;i*10<=10000&&q.size()<n;++i){
        if(i*10%6==0)continue;
        q.push_back(i*10);
    }
    for(ll i=2;i*15<=10000&&q.size()<n;++i){
        if(i*15%6==0||i*15%10==0)continue;
        q.push_back(i*15);
    }
    for(auto x:q)write(x);
}
signed main(){
    ll t=1;
    while(t--){
        solve();
    }
    // fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}