수열

Summary

수열 공식은 구현보다 overflow가 더 위험하다.
합은 long으로 계산한다.

---

등차수열 합

long sum = (long) n * (first + last) / 2;

1부터 n까지 합:

long sum = (long) n * (n + 1) / 2;

---

등비수열 합

Warning

등비수열은 값이 매우 빨리 커진다.
mod가 있으면 매 곱셈마다 mod를 적용한다.

long sum = 0;
long cur = first;
 
for (int i = 0; i < n; i++) {
    sum += cur;
    cur *= ratio;
}

mod가 있는 경우:

long sum = 0;
long cur = first % mod;
 
for (int i = 0; i < n; i++) {
    sum = (sum + cur) % mod;
    cur = (cur * ratio) % mod;
}

---

주의점

(1 + n) * n / 2는 int overflow 가능
등비수열은 long도 쉽게 넘음
mod 조건이 있으면 중간마다 mod