[일반] G번 어케푸는거임?

[secre(182.231)]

접근자체가 안되네 

F보다 훨씬 어려운거같은데 어케 푼사람수는 더 많은거누 

[펜져(penzer27)]

나 WA 하나 때매 못품

[secre(182.231)]

어케접근함?

[펜져(penzer27)]

일단 전부 다 보는 접근에서, sqrt 보고 같은 sqrt 나오는 애들을 묶어서 처리 + 메모이제이션으로 1000만까지 처리로 시간 줄임

[secre(182.231)]

수학 + dp였네 ㅠㅠ

[펜져(penzer27)]

코드 올려볼게 ㄱㄷ 근데 엣코더 틀린 TC 어케보냐 ㄹㅇ 암걸리네 ㅋㅋ

[지피지기(knon0501)]

22번 테케냐? 나도 하나 틀리더라 ㅋㅋㅋ

[secre(182.231)]

혹시 E번 증명은 어케하는지 알음? 대충 플로이드 돌렸는데 왜 통과되는지 모르겠다 아직도

[펜져(penzer27)]

ㅇㅇ 22번

[대학원오지마세요(publfl)]

sqrt의 sqrt이 60000만보다 작아서, 60000만 이하 전처리 한뒤에 몇번 쓰이나 보면 됨. 엄밀하게는, N이 주어질때 M = [sqrt(N)]이라고 하면, 각 1<=i<=60000에 대해서 i는 첫번째 연산후 나온 숫자가 i*i~M사이일때 나올 가능성이 있음. 따라서 (i부터 수열 만드는 경우의수) * (M-i*i+1)을 모든 1<=i<=60000에 대해서 더하면 됨.

[secre(182.231)]

이런거 연습하려면 뭘 풀어야되는거지... ㄳㄳ