Hướng dẫn giải của Số đối lập (Đề Quảng Trị 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
Với mỗi số a, ta tính số ngược r (đảo thứ tự các chữ số). Số a là số đối lập khi a và r nguyên tố cùng nhau, tức ước chung lớn nhất gcd(a, r) = 1. Lưu ý r có thể nhỏ hơn a (ví dụ 120 cho r = 21), dùng long long cho an toàn.
Sub 1: Vét cạn — ~O(a)~
Đảo chữ số để được r, rồi thử mọi ước d từ 2 đến min(a, r). Nếu tồn tại d chia hết cả a lẫn r thì không nguyên tố cùng nhau và in 0, ngược lại in 1. Đúng nhưng với a lên đến 2·10^9 thì quá chậm.
Kết quả chấm: đạt 9/15 test (6 test còn lại quá giờ, không sai).
#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 n;
cin >> n;
while (n--) {
long long a;
cin >> a;
// Tinh so nguoc r bang cach lay chu so cuoi cung dan
long long r = 0, t = a;
while (t > 0) {
r = r * 10 + t % 10;
t /= 10;
}
// Vet can: thu moi uoc d >= 2 xem co chia het ca a va r khong
bool coprime = true;
long long lim = min(a, r);
for (long long d = 2; d <= lim; d++)
if (a % d == 0 && r % d == 0) {
coprime = false;
break;
}
cout << (coprime ? 1 : 0) << "\n";
}
return 0;
}
Sub 2: Thuật toán Euclid — ~O(log a)~
Dùng hàm __gcd (thuật toán Euclid: gcd(a, b) = gcd(b, a mod b)) để tính UCLN của a và r trong thời gian logarit. Nếu bằng 1 thì in 1, ngược lại in 0. Đảo số bằng vòng lặp chia 10 với biến long long.
Kết quả chấm: đạt 15/15 test.
#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 n;
cin >> n;
while (n--) {
long long a;
cin >> a;
// Dao nguoc cac chu so cua a de duoc so r
long long r = 0, t = a;
while (t > 0) {
r = r * 10 + t % 10;
t /= 10;
}
// Hai so nguyen to cung nhau khi UCLN bang 1 (thuat toan Euclid)
cout << (__gcd(a, r) == 1 ? 1 : 0) << "\n";
}
return 0;
}
Bình luận