Tổng các số chính phương chia cho 3 dư 1
Số chính phương là một số tự nhiên sao cho tồn tại một số tự nhiên bình phương bằng nó ví dụ \(0, 1, 4, 9, 16, ...\)
Bài toán đặt ra: Cho số tự nhiên \(n\) hãy tính tổng tất cả các số chính phương chia cho 3 dư 1 và nhỏ hơn hoặc bằng \(n\)
Input
Dòng đầu là số bộ test \(t (1 \le t \le 100)\)
\(t\) dòng tiếp theo mỗi dòng chứa một số tự nhiên \(n\) không vượt quá \(10^9\)
Output
Gồm t dòng mỗi dòng là kết quả bài toán vì số quá lớn nên ta chỉ lấy phần dư của kết quả chia cho 1000000007 \((10^9+7)\)
Ví dụ
Input
3
10
36
37Output
5
46
46Giải thích
Với \(n=10\) ta có các số chính phương nhỏ hơn \(10\) chia cho 3 dư 1 là \(0 ,1 ,4 \) có tổng \(5\)
Với \(n=36\) hoặc \(n=37\) ta có các số chính phương nhỏ hơn \(n\) chia cho 3 dư 1 là \(0 ,1 ,4, 16, 25 \) có tổng \(46\)
Chú ý Đây là bài dễ bài khó hơn tại Lại là tổng các số chính phương chia cho 3 dư 1
Comments
Bài này hình như test có số to hơn 10^9 thầy ạ