PASS486 시간초과에 대하여 질문드립니다. kikiya PASS486 pass486 문제를 풀고 있는데요. 마지막 200 100000 2000000의 경우 아예 답이 안나올 정도로 시간이 오래 걸리고 있습니다. 단순하게 lo부터 hi까지 모든 경우를 모든 수로 나누어서 약수의 개수를 찾는 방식을 취하고 있는데요 처음부터 접근 방식 자체가 틀린 것일까요?? int password(void); int main(void) { int c; scanf("%d", &c); for (int i = 1; i <= c; i++) { password(); } return 0; } int password(void) { int n, lo, hi; int num=0; int kiki = 0; scanf("%d %d %d", &n, &lo, &hi); if (n > 400) return 1; if (hi < 1 && hi>1000000) return 1; if (lo < 1 && lo>1000000) return 1; if (lo > hi) return 1; for (int i = lo; i <= hi; i++) { for (int j = 1; j <= i; j++) { if (i%j == 0) num++; // printf("%d %d \t%d\n", i,j,num); } if (n == (num)) kiki++; num = 0; } printf("%d\n", kiki); return 1; } 8년 전
1개의 댓글이 있습니다. hyunhwan x라는 자연수가 2^a \times 3^b \times 5^c \times \dots 와 같은 소수(prime number)로 표현된다면 (a+1) (b+1) (c+1) \dots 는 해당 숫자의 약수의 수가 됩니다. 에라토스 테네스 체를 응용하면 쉽게 풀릴 수 있습니다. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kikiya
PASS486
pass486 문제를 풀고 있는데요.
마지막 200 100000 2000000의 경우 아예 답이 안나올 정도로 시간이 오래 걸리고 있습니다.
단순하게 lo부터 hi까지 모든 경우를 모든 수로 나누어서 약수의 개수를 찾는 방식을 취하고 있는데요
처음부터 접근 방식 자체가 틀린 것일까요??
8년 전