글 읽기 - 시간 초과 도움좀 주세요 ㅜㅜ

dudrhkd7811 1년 전 0

시간 초과를 해결할 방법을 모르겠습니다. 여러 시도는 해봤는데 어렵습니다.... 고수님들 도와주세요

#include <iostream>
using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		long long int num;
		int cnt = 0;
		cin >> num;
		for (long long int j = 1; j * j <= num; j++) {
			if (num % j == 0)
				cnt++;
		}

		if (cnt % 2 == 0)
			cout << "0 ";
		else
			cout << "1 ";
	}
}

djm03178 1년 전 0

주어지는 수의 범위가 10^18로 매우 크기 때문에 루트까지만 해보더라도 10^9로 시간 내에 돌기는 어렵습니다.

또한 이 코드는 답도 틀립니다. 아래 케이스에 대한 정답은 1입니다.

https://ideone.com/IrrQjz

saberia404 1년 전 0

약수를 일일히 구해서 그 값을 홀수인지 짝수인지 판별하는 것은 시간이 오버되는 것이 맞습니다. 어떤 특정한 수들의 종류의 약수가 홀수인지 짝수인지 생각해보는 것이 좋을 것 같습니다. ex) 소수의 약수는 전부 1과 자신 둘뿐입니다.

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

문제

문제

출처

ICPC

시간 초과 도움좀 주세요 ㅜㅜ

dudrhkd7811 1년 전 0

djm03178 1년 전 0

saberia404 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말