BOJ 25908 - 수열의 합

BOJ 25908 - 수열의 합

약수를 세는 것을 배수를 세는 것으로 변환해서 푸는 문제

1 부터 x 까지 각 숫자가 [1, x] 범위에 몇개의 배수가 있는지 센 후(x/i), 그만큼 i가 짝수라면 더해주고 홀수라면 빼준다.

ll cnt(int x) {  
   ll ret = 0;  
   for (int i = 1; i <= x; i++) {  
      ret += x / i * ((i & 1) ? -1 : 1);  
   }  
   return ret;  
}  
  
void solve() {  
   int s, t;  
   cin >> s >> t;  
   cout << cnt(t) - cnt(s - 1);  
}

더 빠르게 풀기

위의 코드는 $O(N)$ 인데, 조화 수열을 사용하면 더 빠르게 풀 수 있다.

우선, $\left\lfloor \dfrac xi \right\rfloor$ 가 동일한 수의 개수는 $O(\sqrt{x})$ 이다.

이때, $\left\lfloor \dfrac xi \right\rfloor$ 가 같은 $i$ 들의 집합의 구간을 $[l, r]$ 이라 할 때,

이 구간에 짝수와 홀수의 개수를 세서 $\left\lfloor \dfrac x{\left\lfloor \dfrac xi \right\rfloor} \right\rfloor$ 개만큼 짝수라면 더해주고 홀수라면 빼줘서 결국 시간복잡도 $O(\sqrt{N})$ 에 해결 가능하다.

ll cnt(int x) {  
   ll ret = 0;  
   for (int l = 1, r; l <= x; l = r + 1) {  
      int cnt = x / l;  
      r = x / (x / l);  
      int len = r - l + 1;  
      int even = r / 2 - (l - 1) / 2;  
      int odd = len - even;  
  
      ret += ll(even - odd) * cnt;  
   }  
   return ret;  
}  
  
void solve() {  
   int s, t;  
   cin >> s >> t;  
   cout << cnt(t) - cnt(s - 1);  
}