Codeforces Global Round 17/ D. Not Quite Lee

정수론 문제다. 
본대회때는 못풀었는데 똑같은 풀이를 "잘"구현하면 되는데 구현을 못해서 틀렸다.

 

풀이는 똑같다.

 

 

 

 

 

$f(n)=n*(n+1)/2$라고 하자.

 

고른 $k$개의 sequence $a_1$ ~ $a_k$의 합을 적절히 0으로 만들수 있다는 것은,

$gcd(a_1,a_2,\cdots,a_k)$가 $f(a_1)+f(a_2)+\cdots f(a_k)$ 를 나눈다는 것과 정확히 동치이다.

(옮긴 수를 옮기면 되므로)

 

그래서 우리는, gcd를 구해서 합을 나눌 수 있는지를 살펴보는 문제로 바뀌는데, 홀수가 있는 경우에는 항상 가능하다. 따라서 모든 수가 짝수인 부분 수열 중에 $gcd$가 $f(a_i)$합을 나누는지를 살펴보자.

 

그런데  $(n*(n+1)/2)=n/2$ (mod n) 이다. (n은 짝수이므로) 

이거 진짜 멋진 성질인거 같다. 웰노운인가?

 

따라서 $2^k$로 나눌 수 있을때까지 $k$를 최대한 키우고, 작은거부터 배열을 처리하면 $O(32*n)$에 해결가능하다.

근데 이거 구현이 약간 헷갈리는데 dp처럼 하면된다.

 

글을 더 자세히 쓰고 싶은데 다음에 시간되면 보안하겠다.