【cf】#681 A. Kids Seating (Div. 2, based on VK Cup 2019-2020 - Final)

A. Kids Seating

• Yes 1 To 4n Number , Ask to find out n Number , Make any two numbers not coprime and not divisible .

Their thinking

• A construction problem .
• n The scale is 100, Just do it violently .
• It can be found that the first number must be at least from 4 Start . Then traverse 4*n Number , For each number , Find out whether he is coprime with the previous number , And whether there is an integer division relationship with the previous number . For divisible Relations , You can sift every time you find an integer division relationship , This can improve efficiency .
• Traverse 4*n After the count , Judge whether the number found meets n Number , If not enough n, So from 5 Start as the first number …… And so on .
• keyword ： Violent structure

•    Here are some definitions ：
    * pos[]： Initialize to 1,0 It means that it does not meet the requirements 
    * ans[]： Record the numbers that meet the requirements 
    * cnt： Indicates how many numbers currently meet the requirements 
    * j： The first number 
    * check(a)： take a Multiple of pos[] They are all marked with 0, Because there is an integer division relationship , So it doesn't meet the requirements , Marked as 0.
    * check2(a, cnt)： Judge a Whether it meets the requirements of the previous cnt There is a reciprocal relationship between numbers , If coprime , return 1, Otherwise return to 0.
  

Be careful

• If you find that you cannot find n A digital , want j++ When looking for it from the beginning , Remember to reinitialize pos[] and ans[].

skill

• __gcd(a,b)： return a,b Maximum common divisor of .
  Judge a,b Whether two numbers are mutually prime ： Judgment __gcd(a,b) == 1

My code

#include<bits/stdc++.h>
using namespace std;
int n, cnt;
int a[4005], pos[4005], ans[1005];
void check(int a){
    
	for(int i = a; i <= 4*n; i+=a){
    
		pos[i] = 0;
	}
}

int check2(int a, int cnt){
    
	for(int i = 0; i <= cnt; i++)
		if(__gcd(a, ans[i]) == 1)	
			return 1;
	return 0;
} 
int main(){
    
	int t;
	cin >> t;
	while(t--){
    
		cin >> n;
		cnt = 0;
		int j = 4;
		while(j < 4*n){
    	
			memset(ans, 0, sizeof(ans));
			memset(pos, 1, sizeof(pos));
			ans[cnt] = j;
			check(j);
			for(int i = j+1; i <= 4*n; i++){
    
				if(check2(i, cnt)){
    
					continue;
				}
				if(i % ans[cnt] == 0){
    
					check(i); continue;
				}
				if(pos[i] == 0)	continue;
				ans[++cnt] = i;
				check(i);
				if(cnt == n-1)	break;
			}
			if(cnt < n-1){
    
				j++;
				memset(ans, 0, sizeof(ans));
				cnt = 0;
				continue;
			}
			else break;
		}
		if(n == 1){
    
			cout << 1 << endl;
		}
		else{
    
			for(int i = 0; i <= cnt; i++)
				cout << ans[i] << " ";
			cout << endl;
		}
	}
	
	
} 

Optimize

• keyword ： thinking 、 structure

• Code