글 읽기 - 시간초과

gs25 2년 전 0

문제를 간략히 설명하면 다음과 같습니다. 집합이 주어졌을 때 쌍마다 서로소이고 크기가 4인부분집합의 개수를 구하시오. 제 풀이는 뫼비우스 함수를 이용해서 다음같이 풀었습니다. n <= 10^4 이고 시간복잡도가 O(n^2) 인데 시간초과가 뜨네요.. 어떻게 시간복잡도를 줄일 수 있는지 궁금합니다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int mob[10100] = {};

void set_mob(void) {
	mob[1] = 1;
	for (int i = 1; i < 10100; i++) {
		if (mob[i]) {
			for (int j = i * 2; j < 10100; j=j+i) {
				mob[j] -= mob[i];
			}
		}
	}
}

ll N;
ll arr[10100] = {};

int main(void) {
	//cout << (4 * 3 * 2 * 1) / 24;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	set_mob();
	//cout << mob[2];
	while (!cin.eof()) {
		cin >> N;
		for (int i = 0; i < N; i++) cin >> arr[i];
		ll S = 0;
		for (int g = 1; g <= 10000; g++) {
			int gn_ = 0;
			
			if (mob[g]) {
				for (int i = 0; i < N; i++) if (arr[i] % g == 0) gn_++;
				ll gn = gn_;
				ll u = (((((gn * (gn - 1)) / 2) * (gn - 2)) / 3) * (gn - 3)) / 4;
				//cout << u << "\n";
				//if (g == 1) cout << (ull)u<<"\n";
				S += mob[g] * u;
				//if (g == 1) cout << S << "\n";
			}
		}
		cout << (ll)S << "\n";
	}
}

zigui 2년 전 1

38번째 줄에서 모든 g에 대해 모든 원소를 순회하는 것 대신, 모든 수의 약수 g를 구해 배열에 값을 1 더하는 식으로 하면 시간을 줄일 수 있습니다.

추가로, 뫼비우스 함수의 값이 0이 아닌 약수만 구하여 배열을 갱신하면 모든 약수를 확인할 필요가 없어 시간을 더 줄일 수 있습니다.

gs25 2년 전 0

진짜 감사합니다 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과

gs25 2년 전 0

zigui 2년 전 1

gs25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말