SW Expert Academy 5213. 진수의 홀수 약수 D4

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

이 문제에서 가장 중요한건 다름이 아니라

문제의 조건인 100000개 테스트케이스를 합쳐서 5초이내에 계산이 돼야된다는 점이다.

고로 주어지는 숫자 n까지의 홀수 약수의 합을 미리 구해 저장해놓은다음

문제에서 L과R을 제시하면 저장해놓은 memo 배열에서

memo[R] - memo[L-1]을 해서 바로 숫자가 나올 수 있도록 해야한다.

이렇게 하면 미리 memo배열에 숫자를 넣는 과정에는 약간의 시간이 걸리지만

그 후에는 아주 근소한 시간밖에 걸리지 않으므로 문제를 풀 수 있다.

#include <iostream>
#include <cmath>
 
#define num 1000000
 
long long memo[1000001];
using namespace std;
void function()
{
    for (int k = 2; k <= 1000000; k++) {
        long long result = 0;
        int last = (int)sqrt(k);
        for (int i = 1; i <= last; i++) {
            if (k % i == 0) {
                if (i % 2 == 1) result += i;
                long long num2 = k / i;
                if (num2 == i) break;
                else if (num2 % 2 == 1) result += num2;
            }
        }
        memo[k] = memo[k - 1] + result;
    }
}
int main()
{
    long long ans; int count = 0;
    int testcase;
    scanf("%d", &testcase);
    memo[1] = 1;
    function();
    while (testcase--) {
        ans = 0;
        int L, R;
        scanf("%d %d", &L, &R);
 
        printf("#%d %lld\n", ++count, memo[R] - memo[L - 1]);
    }
}