백준 28427 Tricknology

문제

28427번: Tricknology (acmicpc.net)

28427번: Tricknology

 

풀이

x부터 y까지의 합은 초항이 x이고 공차가 1이며 항의개수가 y-x+1인 등차수열의 합 공식으로 나타낼 수 있다.

sum = (y-x+1)(x+y)/2

이것이 소수가 돼야한다. 

(y-x+1)(x+y) = 2*소수 로 나타낼 수 있다.

1. y-x+1이 소수인 경우

x+y(처음과 마지막의 합)는 2가 된다. 이는 불가능하다.

2. x+y가 소수인 경우

y-x+1(항의 개수)이 2가된다.

 

즉 우리가 볼건 x <= 499999에 대해 x + x + 1이 소수인지 아닌지 알아보는 것이다.

이는 반복문으로 순회하면서 sqrt복잡도로 소수판별을 하는 알고리즘을 쓰면 된다.

x + x + 1이 소수라면 arr[x] = 1 이런식으로 마킹을 해준다.

쿼리가 여러개 들어오므로 각 쿼리마다 개수를 구한다면 시간초과가 날 것이다.

따라서 누적합을 이용해 쿼리를 O(1)로 처리한다.

arr을 순회하면서 arr[i] = arr[i-1] + arr[i]를 해준다.

주의해야할것은 arr[i]는 i+1의 정보가 들어갔으므로 누적합으로 쿼리를 처리할 때 arr[R-1] - arr[L-1]로 구해줘야한다는 것이다.