Tổng các số chính phương chia cho 3 dư 1

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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≤t≤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á 109

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 (109+7)

Ví dụ

Input

Copy
3
10
36
37

Output

Copy
5
46
46

Giả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

tichpx

Comments


  • 4
    DuyAnhhh  commented on Sept. 21, 2020, 3:41 p.m.

    Bài này hình như test có số to hơn 10^9 thầy ạ