백준 1419 등차수열의 합

문제

https://www.acmicpc.net/problem/1419

1419번: 등차수열의 합

 

풀이

l <= Kx + d * K * (K - 1) / 2 <= r 을 만족해야한다.

K의 범위가 좁으므로 하나씩 생각할 수 있다.

 Kx + d * K * (K - 1) / 2 에 K = 2,3,4,5를 넣어주자.

1. K = 2

l <= 2x + d <= r

2x + d는 3이상 자연수이다.

2. K = 3

l <= 3(x+d) <= r

3(x+d)는 6이상 3의 배수이다.

3. K = 4

이게 좀 더럽다.

4x + 6d 

이해를 위해 x와 d에 수 몇개를 넣어보자.

X\D	1	2	3
1	10	16	22
2	14	20	26
3	18	24	30

4 < 6이므로 4x + 6d에서 4x부분은 6d의 나머지가 될 것이다.

4x % 6는 0,2,4가 나올 수 있다.(12%6,8%6,4%6)

따라서 4x+6d는 10이상 6으로 나눴을때 나머지가 4인 자연수 or 14이상 6으로 나눴을때 나머지가 2인 자연수 or 18이상 6의 배수이다.

 

4. K = 5

5x + 10d

5(x+2d)

2x+d가 3이상 자연수이므로 x+2d도 3이상 자연수이다.

따라서 5(x+2d)는 15이상 5의 배수이다.

 

# L~R까지 K의 배수를 구하는 법
# 만약에 나머지가 나올 경우 나머지를 올려 다음배수를 보도록 한다. 정수 나눗셈은 버림연산이기 때문이다.
X = L // K if K % K == 0 else 1 + L // K 
Y = R // K
diff = Y - X + 1

 

# L~R까지 K로 나눴을 때 나머지가 REST인 수를 구하는 법
# L과 R을 Kq + REST꼴로 바꾼다. 
# L은 + R은 -해줘야 범위를 안벗어난다.
lr = L % K
L += REST - lr if REST >= lr else K + REST - lr
rr = R % K
R -= rr - REST if REST <= rr else rr + K - REST
# 이를 쉬프트 시킨다.
L -= REST
R -= REST
# 이제 K의 배수 개수를 구하는 코드를 L,R에 적용
X = L // K if K % K == 0 else 1 + L // K 
Y = R // K
diff = Y - X + 1