진수의 홀수 약수

5213. 진수의 홀수 약수

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-hF8KdBADFAVT

범위가 1,000,000이라 그냥 구하면 시간초과.

[1]

미리 홀수약수의 합을 memo[]에 구해놓는다. 

배수를 이용한다.

[2]

미리 홀수약수 합들을 구해놔도 범위를 많이주면 찾는데 오래걸린다.

부분합을 미리 구해놓는다.

검색해보니 인덱스트리를 이용하는 방법도 있던데, 그냥 부분합만 구해도 통과된다.

package com.company;

import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static int NUM = 1000000;

    public static void main(String[] args) {

        //홀수인 약수 합을 미리 구해놓는다( 3의 배수는 모두 3을 약수로 가진다 -> 3,6,9,12,15...  )
        int[] memo = new int[NUM +1];

        for(int i = 1; i<= NUM; i+=2){
            for(int j = 1; j<= NUM/i; j++){
                memo[i*j] += i;
            }
        }


        //부분까지의 합을 미리 구해놓는다 S(n) = S(n-1) + a(n)
        long[] sum = new long[NUM +1];

        sum[1] = memo[1];
        for(int i = 2; i<= NUM; i++){
            sum[i] = sum[i-1] + memo[i];
        }



        //홀수합을 구한다
        int T = sc.nextInt();
        int a,b;

        for(int i=1; i<=T; i++){
            a = sc.nextInt();
            b = sc.nextInt();

            long result= sum[b] - sum[a-1];
            System.out.println("#" + i + " " + result);
        }

    }//main
}