Hướng dẫn giải của [200 đề thầy Đức] Bài 90: Chia
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
Từ $n$ ta chỉ có ba thao tác: chia đôi (khi $n$ chia hết cho $2$), nhân $2/3$ (khi $n$ chia hết cho $3$), nhân $4/5$ (khi $n$ chia hết cho $5$). Mỗi thao tác làm giá trị nhỏ đi, và cần tìm số thao tác ít nhất để về $1$, hoặc báo $-1$.
Sub 1: Vét cạn bằng BFS — ~O(\text{số trạng thái})~, dùng khi ~n \le 10^6~
Coi mỗi giá trị là một đỉnh, mỗi thao tác là một cạnh, và tìm đường đi ngắn nhất từ $n$ đến $1$ bằng BFS. Các giá trị đi qua luôn có dạng $2^x 3^y 5^z$ nên số trạng thái nhỏ.
Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Công thức theo thừa số nguyên tố — ~O(\log n)~
Viết $n = 2^a \cdot 3^b \cdot 5^c \cdot m$. Các thao tác không làm đổi phần $m$, nên $m$ phải bằng $1$, nếu không thì đáp án là $-1$.
Khi $m = 1$: cần đúng $b$ lần thao tác $2/3$ và $c$ lần thao tác $4/5$. Thao tác $2/3$ làm số mũ của $2$ tăng $1$, còn thao tác $4/5$ làm số mũ của $2$ tăng $2$. Để đưa số mũ của $2$ về $0$ cần $x = a + b + 2c$ lần chia đôi. Tổng số thao tác là $x + b + c = a + 2b + 3c$.
Thứ tự thực hiện: làm hết các thao tác $2/3$ và $4/5$ trước rồi mới chia đôi, vì các thao tác này không cần số mũ của $2$ giảm đi nên luôn thực hiện được.
Bẫy cần chú ý: $n$ đến $10^{18}$, nên dùng long long.
Chương trình hoàn chỉnh
Chương trình đọc $q$ truy vấn. Nếu mọi $n \le 10^6$ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int q;
vector<long long> ns; // các truy vấn n
// BFS trên các giá trị: mỗi thao tác đưa n về giá trị nhỏ hơn, các trạng thái có dạng 2^x 3^y 5^z
// nên số trạng thái ít. Trả về số thao tác tối thiểu để về 1, hoặc -1.
long long bfsDist(long long start) {
map<long long, long long> dist;
queue<long long> qu;
dist[start] = 0;
qu.push(start);
while (!qu.empty()) {
long long x = qu.front(); qu.pop();
if (x == 1) return dist[x];
long long nxt[3];
int cnt = 0;
if (x % 2 == 0) nxt[cnt++] = x / 2; // thao tác 1
if (x % 3 == 0) nxt[cnt++] = 2 * (x / 3); // thao tác 2: 2n/3
if (x % 5 == 0) nxt[cnt++] = 4 * (x / 5); // thao tác 3: 4n/5
for (int i = 0; i < cnt; i++)
if (!dist.count(nxt[i])) {
dist[nxt[i]] = dist[x] + 1;
qu.push(nxt[i]);
}
}
return -1; // không về được 1
}
// Sub 1: vét cạn — BFS cho từng truy vấn. Dùng khi mọi n <= 10^6
void sub1() {
for (int i = 0; i < q; i++) cout << bfsDist(ns[i]) << "\n";
}
// Sub 2: công thức. Viết n = 2^a * 3^b * 5^c * m. Các thao tác không làm đổi m,
// nên m phải bằng 1 (nếu còn thừa số nguyên tố khác thì không thể đưa về 1).
// Cần: b lần thao tác 2 (mỗi lần cũng làm a tăng 1), c lần thao tác 3 (mỗi lần làm a tăng 2),
// và x lần thao tác 1 với x = a + b + 2c. Tổng = a + 2b + 3c.
void sub2() {
for (int i = 0; i < q; i++) {
long long x = ns[i], a = 0, b = 0, c = 0;
while (x % 2 == 0) { x /= 2; a++; }
while (x % 3 == 0) { x /= 3; b++; }
while (x % 5 == 0) { x /= 5; c++; }
if (x != 1) cout << -1 << "\n";
else cout << a + 2 * b + 3 * c << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> q;
ns.resize(q);
bool small = true;
for (int i = 0; i < q; i++) {
cin >> ns[i];
if (ns[i] > 1000000) small = false;
}
if (small) sub1(); // n nhỏ: BFS
else sub2(); // n lớn: công thức
return 0;
}
Bình luận