Tổng chính phương
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
0.6s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Người đăng:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Số chính phương được định nghĩa là bình phương của một số nguyên.
Yêu cầu: Với số n cho trước, hãy tính tổng các số chính phương trong đoạn từ 1 đến n.
Input
- Dòng đầu tiên chứa q ~(q \le 10^4)~ - số truy vấn.
- q dòng tiếp mỗi dòng chứa số nguyên dương n ~(n \le 10^{18})~
Output
- Mỗi dòng chứa tổng S sau khi đã mod cho ~10^9 + 7~
Example
Input:
1
1
Output:
1
Bình luận
wow
chúc Anh Em 8386 vạn sự như ý, triệu sự như mơ, tỷ sự bất ngờ ngập tràn may mắn chúc Anh Em MÃI ĐỈNH MÃI ĐỈNH MÃI ĐỈNH LUÔN
Solution By Shinoz
Hint 1:
Đề yêu cầu: tính số chính phương từ ~1~ -> ~n~ với ~n~ bất kì trong đoạn ~1~ -> ~10^{18}~
Ta thấy: số chính phương gấn n nhất là: ~sqrt(n)~ (chỉ lấy phần nguyên)
Đặt ~m = sqrt(n)~. Ta có công thức tính bình phương từ ~1~ -> ~m = m(m + 1)(2m + 1)~
có thể tìm kiếm trên mạng
Hint 2:
Việc tính ~maxn = 10^{18}~ hay ~= 10^{9}~ (sau khi lấy căn) sẽ làm tràn số nên ta phải sử dụng tính chất đồng dư modulo / nghịch đảo modulo
Modular arithmetic:
Có thể bị sai số khi sử dụng nên ta phải kiểm tra x * y mod 6 = 0 ?
M ~= 10^{9} + 7~
TH1: m * (m + 1) mod 6 = 0
TH2: m * (2m + 1) mod 6 = 0
TH3: (m + 1)(2m + 1) mod 6 = 0
Modular multiplicative inverse:
Ngược lại với cộng / nhân, (a / b) mod M có thể sẽ khác(a mod M) / (b mod M)
Ta có:
(a / b) mod M = (a * ~b^{-1}~) mod M = (a mod M) * (~b^{-1}~ mod M) mod M
Vì M là số nguyên tố nên theo định lý Fermat, ta có: ~b^{-1}~ mod M = ~b^{(M - 2)}~
Chỉ hoạt động khi M là số nguyên tố
Có thể tính trước ~6^{M - 2}~ rồi lắp vào công thức tính (sử dụng AI / search google / sử dụng chia để trị)
Document
Modular arithmetic
Modular multiplicative inverse
Another solution
Chất quá Shinoz ơi!
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
ngầu quá ngầu quá nma sol thiếu sót vl
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
nghịch đảo modulo (tuy không cần thiết vì vẫn dùng tính chất đồng dư được)