CF1443A Kids Seating 暴力埃筛

老年人又回来打CF了，但是因为养生，熬不起夜，还是打打VP吧。

传送门：https://codeforces.com/contest/1443/problem/A

题意：

老师要给n个孩子安排座位，总共有4n个座位从1到4n编号，但是，如果两个孩子的座位编号互质，或者一个是另一个的倍数，这两个孩子就会开始折腾，找出一种让所有孩子都不折腾的座位安排方法。

题解：

按如下步骤暴力求解：

1，首先划掉所有奇数的座位，因为所有奇数都跟至少一个偶数互质。

2，让第一个孩子坐在2号座位上，划掉所有2的倍数

3，找到下一个没有被划掉的座位，让下一个孩子坐上去，并划掉所有它的倍数，以此类推

4，如果座位够就ok了，否则，回到第2步，只不过2号座位不要坐了，从4号开始，再不行就从6号开始，以此类推

代码：

#include<bits/stdc++.h>
using namespace std;
bool ans[401];
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d",&n);
        int nn=n;
        memset(ans,0,sizeof ans);
        vector<int> ansp;
        for(int k=4; k<=4*n; k+=2) {
            memset(ans,0,sizeof ans);
            ansp.clear();
            for(int i=k; i<=4*n && ansp.size()<nn; i+=2) {
                if(ans[i]==0) {
                    //printf("%d%c",i,nn==1?'
':' ');
                    ansp.push_back(i);
                    for(int j=2*i; j<=4*n; j+=i)ans[j]=1;
                }
                //printf("%d%c",,i==n?'
':' ');

            }
            if(ansp.size()==nn) {
                for(int i=0; i<ansp.size(); i++) {
                    printf("%d%c",ansp[i],i==ansp.size()-1?'
':' ');
                }
                break;
            }
        }

    }
    return 0;
}

拓展：

本题由于数据范围较小（$n leq 100$），可以暴力出来，如果数据范围较大，该如何找到第一个孩子的座位？

暴力得出的规律是，当座位数是$4 imes n$时，第一个座位应该放在$left lceil frac{n-1}{3} imes 4 ight ceil$号位置

CF1443A Kids Seating 暴力 埃筛

CF1443A Kids Seating 暴力埃筛