Hướng dẫn giải của [2526 KS CHV] Câu 1: Tổng bình phương
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho q truy vấn, mỗi truy vấn là số nguyên dương N. Hỏi S = 1² + 2² + ... + N² có chia hết cho N hay không (in YES/NO). Bài đọc từ file CAU1.INP và ghi ra CAU1.OUT.
Sub 1: Cộng trực tiếp rồi lấy dư — ~O(N) mỗi truy vấn~
Với mỗi truy vấn, cộng dần i² (lấy mod N sau mỗi bước để không tràn số) rồi kiểm tra dư bằng 0. Đúng nhưng chậm, chỉ đạt 13/24 test (các test có N nhỏ); các test N lớn bị TLE.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int q;
cin >> q;
while (q--) {
long long n;
cin >> n;
// Sub 1: cong truc tiep S = 1^2 + ... + N^2 roi lay phan du mod N (vet can)
long long s = 0;
for (long long i = 1; i <= n; i++) s = (s + i * i % n) % n;
cout << (s == 0 ? "YES" : "NO") << "\n";
}
return 0;
}
Sub 2: Công thức S = N(N+1)(2N+1)/6 — ~O(1) mỗi truy vấn~
Dùng công thức S = N(N+1)(2N+1)/6. Với N ≤ 10^9, tích ba thừa số lên tới khoảng 2·10^27 nên không vừa long long (có thể dùng __int128, nhưng chậm hơn). Thủ thuật: chia trước 2 và 3 vào các thừa số trước khi nhân.
- Trong N và N+1 có đúng một số chẵn, chia 2 cho số đó.
- Trong ba thừa số (đã chia 2) có đúng một số chia hết cho 3, chia 3 cho số đó.
- Khi đó S = x·y·z là số nguyên, và ta chỉ cần (x mod N)·(y mod N)·(z mod N) mod N, mỗi tích không vượt quá 10^18.
Bài có nhiều truy vấn (có test 500000 truy vấn) nên đọc và ghi bằng bộ đệm (sync_with_stdio(false), gom kết quả vào chuỗi). Đạt 24/24 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
string out;
while (q--) {
long long n;
cin >> n;
// S = N(N+1)(2N+1)/6. Chia truoc 2 va 3 de khong bi tran so, roi lay mod N.
long long x = n, y = n + 1, z = 2 * n + 1;
if (x % 2 == 0) x /= 2; else y /= 2; // mot trong N, N+1 chan
if (x % 3 == 0) x /= 3; // 3 chia het mot trong ba thua so
else if (y % 3 == 0) y /= 3;
else z /= 3;
long long s = (x % n) * (y % n) % n * (z % n) % n; // S mod N
out += (s == 0 ? "YES\n" : "NO\n");
}
cout << out;
return 0;
}
Bình luận