Lại là tổng các số chính phương chia cho 3 dư 1

Submit solution
Points: 4 (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 \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^{18}\)

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
37

Output

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 khó còn bài dễ hơn tại Tổng các số chính phương chia 3 dư 1

tichpx

Comments


  • -8
    ToMinhTien_CNTT4_K62  commented on May 19, 2022, 5:34 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 3
    Hoan_CNTT_VA2_K61  commented on May 16, 2022, 7:28 p.m. ← edit 3

    Hình như test case 1 có vấn đề

    • hàm sqrt trong C/C++ khá nhạy cảm và từng gây tranh cãi khi ép kiểu nó sẽ làm tròn số trước khi tới 1e18
      • ...
      • sqrt(999999999999999933) = 999999999
      • sqrt(999999999999999934) = 999999999
      • sqrt(999999999999999935) = 999999999
      • sqrt(999999999999999936) = 1000000000
      • sqrt(999999999999999937) = 1000000000
      • sqrt(999999999999999938) = 1000000000
      • ...
    • Trong test case 1 có:
      • 999999999999999959
      • 999999999999981533
      • 999999999999993666
      • ...

    • Đúng ra nó phải cho ra 3 kết quả giống nhau nhưng vì 9999..59 nó đã làm tròn khi khai căn rồi ép kiểu trong C/C++ nên cho ra kết quả khác

      Code Python m.n xem thử:

    from math import comb, isqrt

M = int(1e9+7)

def ts(x):
    return comb(x+1, 3) + comb(x+2, 3)

def main():
    for i in range(int(input())):
        n = isqrt(int(input()))
        t = int(n/3)
        print((ts(n)%M-(9*ts(t))%M+M)%M)

if __name__ == '__main__':
    main()

    • 6
      TICHPX  commented on May 17, 2022, 9:07 a.m.

      Thầy đã test lại đúng là có vấn đề test 1