Ta có công thức như sau: ~1+2+3+...+n=\frac{(n*(n+1))}{2}~

Giả sử tồn tại một số nguyên dương ~x~ sao cho ~\frac{x*(x+1)}{2} = n~

Subtask 1 (50% số test): ~N≤10^9~

Ta có: ~x∗(x+1) = 2∗n~ ~⇒x< \sqrt{2∗n}~

Vì vậy ta chỉ cần thử hết tất cả các số nguyên dương ~x~ thoả điểu kiện trên

Độ phức tạp ~O(\sqrt{N})~

Subtask 2 (50% số test): ~N≤10^{18}~

Ta có: ~x∗(x+1) = 2∗n~

~x^2 < x∗(x+1) < (x+1)^2~ ~⇒x<\sqrt{2∗n}<(x+1)~

Nhận thấy nếu tồn tại một số ~x~ thoả mãn điều kiện thì ~x = \lfloor\sqrt{2*n}\rfloor~

Độ phức tạp: ~O(1)~