<Algorithm> 179. 진수의 홀수약수(SWExpert)

1. 진수의 홀수약수(SWExpert)

   사용 알고리즘 : 규칙,구간합

• 규칙을 잘 못 찾아서 조금 많이 해맨것 같다. 내가 생각한 규칙이 맞는지 범위를 넓게 가져가서 생각해야 겠다.

문제에 대한 접근&생각

1. N이 100000000 -> 완전탐색 불가!, O(N^2) 불가!
2. 규칙이 존재할 것이라 판단 -> 누적되는 것 같아서 짝수를 2로 홀수는 3으로 나눈 값으로 구현 -> 약수가 4개 넘어갔을때 누적 되지않음
3. 모든 합을 구하되 NlgN으로 구해야함 -> i*j에서 j는 i의 배수를 이용 & i는 홀수이므로 연산↓
4. 답은 L~R에 합을 출력 -> 구간합!

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

import java.util.Arrays; import java.util.Scanner;   public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         /***************************          * 홀수의 약수가 되는 수를 미리 구한후          * 이를 이용해 구간합을 구하고           * 약수합을 출력한다.          ***************************/         long[] nums = new long[1_000_001];         long[] sum = new long[1_000_001];         // 약수의 합 구하기         // i는 약수 i*j는 구하려는 약수         // NlogN         for(int i = 1; i < nums.length; i=i+2) {             for(int j = 1; i*j < nums.length; j++) {                 nums[i*j] +=i;             }         }         sum[0] = nums[0];         for(int i = 1; i<nums.length; i++ ) {             sum[i] = sum[i-1]+nums[i];         }         int test = sc.nextInt();                      for(int t=1; t<=test; t++) {             int L = sc.nextInt();             int R = sc.nextInt();             System.out.println("#"+t+" "+(sum[R]-sum[L-1]));         }     } }   Colored by Color Scripter

cs