Hướng dẫn giải của Cấp số cộng (đề HSG 12 Khánh Hòa 2020-2021)
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
Dãy có số hạng thứ m là um = u1 + (m − 1)·d. Cần tìm m sao cho u_m = x, hoặc báo −1 nếu x không thuộc dãy.
Sub 1: Sinh từng số hạng — ~O(|x − u_1| / |d|)~
Bắt đầu từ u1, cộng dần d và đếm chỉ số. Nếu gặp x thì in chỉ số; nếu đã vượt qua x theo chiều của công sai thì in −1. Đạt 20/20 test nhưng có thể quá giờ khi |x − u1| lớn và |d| nhỏ (khoảng 10^9 bước).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("ARIPOG.INP", "r")) { freopen("ARIPOG.INP", "r", stdin); freopen("ARIPOG.OUT", "w", stdout); }
long long u1, d, x;
cin >> u1 >> d >> x;
// Vét cạn: lần lượt sinh từng số hạng của dãy cho đến khi gặp x hoặc vượt qua x
long long cur = u1, m = 1;
while (true) {
if (cur == x) { cout << m << "\n"; return 0; }
// dãy đã đi quá x theo chiều của công sai thì x không thuộc dãy
if ((d > 0 && cur > x) || (d < 0 && cur < x)) { cout << -1 << "\n"; return 0; }
cur += d;
m++;
}
return 0;
}
Sub 2: Công thức — ~O(1)~
Từ um = x suy ra (x − u1) phải chia hết cho d và thương k = (x − u1)/d phải không âm, khi đó m = k + 1. Cần dùng long long vì hiệu x − u1 có thể lên tới 2·10^9. Với số âm trong C++, nếu (x − u_1) % d == 0 thì phép chia là chính xác. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("ARIPOG.INP", "r")) { freopen("ARIPOG.INP", "r", stdin); freopen("ARIPOG.OUT", "w", stdout); }
long long u1, d, x;
cin >> u1 >> d >> x;
// u_m = u1 + (m-1)*d => m = (x - u1)/d + 1, phải chia hết và m >= 1
long long diff = x - u1;
if (diff % d != 0) { cout << -1 << "\n"; return 0; }
long long k = diff / d; // k = m - 1
if (k < 0) cout << -1 << "\n";
else cout << k + 1 << "\n";
return 0;
}
Bình luận