5213. 진수의 홀수 약수

5213. 진수의 홀수 약수

숫자의 범위가 커서 시간제한이 문제일 것 같았다.

따라서 testcase 를 받기전에 get_f 함수를 통해서 각각의 f[x] 값들을 미리 구해주었다.

그리고 조금 더 시간을 단축하기 위해서 sum 이라는 배열을 통해서 sum[x] 는 1~X 까지 f[X] 의 합을 구했다.

따라서 정답을 구할 때는 sum[R]-sum[L-1] 을 통해서 구할 수 있었다.

get_f 에서 최대 루트 1000000 까지 돌고, main 함수에서 1000000 번 돌기 때문에 1억번으로 시간제한을 통과할 것이라고 생각하고 코드를 

구현하였다.

<정답 코드>

#include<iostream>
 
#define MAX 1000001
using namespace std;
 
long long f[MAX];
long long sum[MAX];
void get_f(int X)
{
    for (int i = 1; i*i <= X; i++)
    {
        if (X%i == 0)
        {
            if (i % 2 == 1)
                f[X] += i;
 
            if (i != (X / i)) {
                if ((X / i) % 2 == 1)
                    f[X] += (X / i);
            }
        }
    }
}
 
int main()
{
 
    for (int i = 1; i < MAX; i++)
    {
        get_f(i);
        sum[i] += (sum[i - 1] + f[i]);
    }
 
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int L, R;
        long long ans = 0;
        cin >> L >> R;
 
        cout << "#" << t << " " << sum[R]-sum[L-1] << endl;
 
    }
    return 0;
}