Mình xin chia sẻ lời giải bài toán này như sau:

Gọi \(f(m)\) là số hình vuông cần tìm, khi đó ta có: \(f(m)=f(m-1)+\sum\limits_{i=0}^{\left \lfloor{\frac{2m-1}{3}}\right \rfloor}2(m-i)-1-i\) với \(f(1)=1\) và \(m\ge 2\)

Trong đó \(2(m-i)-1-i\) chính là số hình vuông có cạnh là \(i+1\).

Từ công thức trên ta có: \(f(m)=f(m-1)+2m * (k(m)+1)-\frac{3k(m)(k(m)+1)}{2}-(k(m)+1)\) với \(k(m)=\left\lfloor{\frac{2m-1}{3}}\right\rfloor,f(1)=1,m\ge 2\).

Từ đây ta dễ dàng duyệt một for để xây dựng mảng \(f(m)\) với \(1\le m\le 5.10^5\)

Như vậy bài toán đã được chứng minh.

Các bạn có thể tham khảo code của mình tại \(\href{https://ideone.com/cMOxeY}{đây}\)