Submission #7158

#	Time	Username	Problem	Language	Result	Execution time	Memory
7158		tncks0121	경비원 (GA8_guard)	C++98	8 / 100	2000 ms	1128 KiB

guard

#include <cstdio>
using namespace std;
 
int gcd (int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int n, a[100], g[100][100], x[100];
 
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", a+i);
	for(int i = 0; i < n; i++) {
		for(int j = i+1; j < n; j++) {
			g[i][j] = g[j][i] = gcd(a[i], a[j]);
		}
	}
 
 
		int res = 0;
	for(int state = 0; state < (1<<n); state++) {
		int c = 0;
		for(int i = 0; i < n; i++) if((state >> i) & 1) x[c++] = i;
		if(c <= 1) continue;
		bool s = true;
		for(int i = 0; i < c && s; i++) {
			for(int j = i+1; j < c && s; j++) {
				if(g[x[i]][x[j]] >= 2) s = false;
			}
		}
		if(s) {
			++res;
		//for(int i = 0; i < c; i++) printf("%s%d%s", (i == 0) ? "{" : "", a[x[i]], ((i == c-1) ? "}\n": ", "));
		}
	}
 
	printf("%d\n", res);
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 27
• Subtask 5: 0 / 36