글 읽기 - 어떤 부분에서 시간초과가 나오는지 감이 안오네요 ㅠ 도와주세요

magpies1221 4년 전 0

1. 우선 에라토스테네스의 체를 이용하여 1000까지의 소수를 구합니다.

2.그다음 각 수들을 소인수 분해 하면서 저장해 주고요 전체 값(모든 수들의 소수들의 개수들)도 같이 구해줍니다.

3. 그리고 마지막에 전체 소수들의 개수를 n으로 나누후에 1 이상의 값이 나오면 모둔 수들의 소수의 차이와 비교하여 cnt해주었습니다.

그러나 7%에서 계속 시간초과가 발생해서요 ㅠㅠ어떤 부분을 줄여야하나요?

#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stack>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

bool che[1002];
int sosu[102][1002];
int res[1002];

vector <int> prime;

int n;
int arr[102];

int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	che[1] = false;
	for(int i = 2; i < 1001; ++i) {
		if (che[i]) continue;
		prime.push_back(i);
		for (int j = 2; j*i < 1001; j++) che[i*j] = true;
	}

	memset(sosu, 0, sizeof(sosu));
	int sizeprime = prime.size();
	int done = 0;
	for (int i = 0; i < n; i++) {
		int temp = arr[i];
		
		while (temp != 1) {
			//cout << temp << '\n';
			for (int j = 0; j < sizeprime;) {
				//cout << temp << ' ' << prime[j] << '\n';
				if (temp%prime[j] == 0) {
					sosu[i][prime[j]]++;
					res[prime[j]]++;
					temp /= prime[j];
					
					if (done == 0 || done < j) done = j;

					if (temp == 1) break;
					continue;
				}
				j++;
			}
		}
	}
	
	long long ress = 1;

	int rescnt = 0;

	for (int i = 0; i <= done; i++) {
		res[prime[i]] /= n;
		if (res[prime[i] == 0]) continue;
		for (int j = 0; j < n; j++) {
			if (res[prime[i]] > sosu[j][prime[i]]) {
				rescnt += res[prime[i]] - sosu[j][prime[i]];
			}
		}
		ress *= pow(prime[i], res[prime[i]]);
	}
	cout<<ress<<'\n' << rescnt;

	return 0;
}

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

문제

문제

출처

ICPC

어떤 부분에서 시간초과가 나오는지 감이 안오네요 ㅠ 도와주세요

magpies1221 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말