BOJ

[BOJ23888] 등차수열과 쿼리 - Python

dojini 2024. 11. 8. 11:11

문제

풀이

다음과 같은 형태의 수열이다.

쿼리 1

쿼리 탐색 길이 n 내에서 계산한다.


다음과 같이 3개의 구역으로 나누어 계산한다.

$$
an + d*n(l-1) + n(n-1)/2
= a*n + d
{n(l-1) + n(n-1)/2)
$$

쿼리 2

d증가에 따라 최대 공배수의 변화가 없다.
그러니 a와 d의 최대 공배수가 탐색할 공차 수열의 최대 공배수 이다.

물론 탐색할 수열의 길이가 1이면 최대 공배수는 수열의 값이다.

import sys, math
ip = lambda:map(int, sys.stdin.readline().split())
a, d = ip()
q, *_ = ip()

g = math.gcd(a,d)

for _ in range(q):
    oper, l, r = ip()
    # 쿼리 1
    if oper == 1:
        # 쿼리 탐색 길이
        n = r-l+1 
        # 계산
        print(n*a + d*(n*(l-1)+(n-1)*n//2))
        continue

    # 쿼리 2
    if l == r:
        print(a+d*(l-1))
    else:
        print(g)

'BOJ' 카테고리의 다른 글

[BOJ3661] 생일 선물 - Python  (0) 2024.11.23
[BOJ17430] 가로등 - Python  (0) 2024.10.31
[BOJ1016] 제곱 ㄴㄴ 수 - Python  (0) 2024.10.30
[BOJ1890] 점프 - Python  (0) 2024.10.28