5213. 진수의 홀수 약수(D4)

 문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-hF8KdBADFAVT&categoryId=AWT-hF8KdBADFAVT&categoryType=CODE

시간을 무려 5초나 준다. 그래서 처음에는 무작정 부딪혔지만 시간초과가 발생했다. 이유는 테스트 케이스가 100,000개라는 것을 못봤기 때문..

지금까지의 문제와는 조금 다른 느낌이었다. 이 문제에서 중요한 것은 10^6개의 숫자에 대해 미리 홀수 약수합을 구해놔야 한다는 것이다. 즉, 미리 데이터를 구해놓고 test_case 루틴에 들어가야 한다는 것이다. 

그 부분만 기억하면 쉽게 풀 수 있는 문제 ! 188ms가 나왔는데 89ms에 푸신 분들은 도대체 어떻게 푸신건지 궁금하다..:(

※ 1000001칸 짜리 arr 배열을 전역변수로 선언하지 않으면 stack overflow가 발생한다 ! stack에 담기에는 많이 무거운 듯 하다.

- 소스코드 -

#define _CRT_SECURE_NO_WARNINGS
 
#include<iostream>
 
using namespace std;
 
long long arr[1000001] = { 0 };
 
int main() {
    int T;
    scanf("%d", &T);
    
    
    for (int i = 1; i <= 1000000; i += 2) {
        for (int j = 1; j <= 1000000 / i; j++) {
            arr[i*j] += i;
        }
    }
    for (int i = 1; i <= 1000000; i++) {
        arr[i] += arr[i - 1];
    }
    
    
 
    for (int test_case = 1; test_case <= T; test_case++) {
        int L, R;
        scanf("%d", &L);
        scanf("%d", &R);
        
        long long result = arr[R] - arr[L-1];
        printf("#%d %lld\n", test_case, result);
    }
 
    return 0;
}