Phân Số
Đề bài
Khi tìm hiểu về Số hữu tỉ, Bờm biết rằng, số hữu tỉ có thể được biểu diễn dưới dạng phân số $X/Y$, trong đó $X$ và $Y$ ($Y \ne 0$) là các số nguyên. Số hữu tỉ cũng được phân thành 2 loại: thập phân hữu hạn hoặc vô hạn tuần hoàn. Ví dụ, số hữu tỉ $116/495 = 0{,}2(34)$ là số thập phân vô hạn tuần hoàn, còn số $3/20 = 0{,}15$ là số thập phân hữu hạn. Với số hữu tỉ $X/Y$, Bờm muốn xác định số hữu tỉ là loại thập phân hữu hạn hay vô hạn tuần hoàn.
Yêu cầu: Cho $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ và $n$ số nguyên dương $b_1, b_2, \ldots, b_n$. Gọi $X = a_1 \times a_2 \times \ldots \times a_n$ và $Y = b_1 \times b_2 \times \ldots \times b_n$. Hãy giúp Bờm xác định phân số $X/Y$ là thập phân hữu hạn hay vô hạn tuần hoàn.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương $T$ ($1 \le T \le 10$) là số lượng bộ dữ liệu.
- $T$ dòng sau, mỗi dòng có khuôn dạng: số đầu tiên mỗi dòng là $n$, tiếp theo là dãy gồm $2 \times n$ số nguyên dương $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ mô tả một bộ dữ liệu. Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả: gồm $T$ dòng, mỗi dòng ghi "finite" hoặc "repeating" tương ứng với câu trả lời phân số $X/Y$ là thập phân hữu hạn hay vô hạn tuần hoàn.
Giới hạn: Gọi $V = \max(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n)$.
- Subtask 1 (25% số điểm): $n = 1$, $V \le 10^6$;
- Subtask 2 (25% số điểm): $n \le 10^4$, $V \le 10^6$;
- Subtask 3 (25% số điểm): $n \le 10^5$, $V \le 10^5$;
- Subtask 4 (25% số điểm): $n \le 10^5$, $V \le 10^6$.
4
2 1 7 5 6
1 3 20
1 4 1
1 116 495repeating
finite
finite
repeatingGiải thích:
| Bộ dữ liệu | Phân số | Giá trị | Kết quả |
|---|---|---|---|
| 2 1 7 5 6 | $7/30$ | $0{,}2(3)$ | repeating |
| 1 3 20 | $3/20$ | $0{,}15$ | finite |
| 1 4 1 | $4/1$ | $4$ | finite |
| 1 116 495 | $116/495$ | $0{,}2(34)$ | repeating |
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Hỏi đápCách của bạn học viên sai ở đâu?
Bạn học viên nhắn cho mình thế này:
Chỗ mà em nói “loại hết 2 và 5 ra khỏi Y”, ý của em là $b_i$ nào là 2 với 5 thì loại ra đúng không? Rồi “số dư của dãy số X với dãy số Y” là sao?
À, ý là tính $Y$ là tích của tất cả các $b_i$ với nhau, sau đó liên tục chia cho 2 và chia cho 5 đến khi nào không chia được nữa? Có vẻ em đang ỷ vào Python xử lý được số lớn nhỉ? 😅
Ủa for 1 lần :))) nhưng đâu có nghĩa độ phức tạp chỉ căn theo số vòng for đâu em.
Anh không rành về Python lắm nhưng chắc chắn việc nhân, chia, cộng, trừ 2 số cực lớn sẽ không phải là $O(1)$. $V$ tối đa $10^6$, có tối đa $10^5$ số. Ví dụ $10^6 \times 10^6 = 10^{12}$ rồi, giờ nhân cả $10^5$ số thì sẽ là $10^{6 \cdot 10^5}$ – một số có tới 600 nghìn chữ số, kinh lắm 😱. Nên là từng $b_i$ chia ra cho 2 và 5 sẽ tốt hơn.
Ý tưởngPhân tích thừa số nguyên tố rồi triệt tiêu
Nhưng mà do anh theo code C++, không hỗ trợ số lớn nên bài này tư tưởng của anh là chẳng cần xử lý số lớn.
Ý tưởng là đi phân tích lần lượt $a_i$ thành tích các thừa số nguyên tố, sau đó đi phân tích lần lượt $b_i$ thành tích các thừa số nguyên tố. Sau đó triệt tiêu tụi nó cho nhau. Lúc này kiểm tra thấy mẫu số có sự tồn tại của số nguyên tố khác 2 và 5 thì kết quả chắc chắn là vô hạn, còn chỉ có 2 và 5 thì là hữu hạn.
Ví dụ: $X = 1 \cdot 7$, $Y = 5 \cdot 6$. Số 1 bỏ qua do nó không $\ge 2$ (số nguyên tố thì $\ge 2$). 7 phân tích ra cũng chỉ được 7. 5 phân tích ra được 5. 6 phân tích ra được $2 \cdot 3$. Vậy tử là $7$, mẫu là $2 \cdot 3 \cdot 5$, không có cái nào triệt tiêu được cả. Thấy mẫu có sự xuất hiện của 3 (khác 2 và 5) ⇒ vô hạn.
Tức là chúng ta phải đề phòng tình huống mẫu số khi phân tích có sự xuất hiện của 1 thừa số nguyên tố khác 2 và 5, ví dụ số 3 hay 7, thì lúc này phải xem có thể triệt tiêu 3 hay 7 đó nhờ tử số không.
Ví dụ tử số sau khi phân tích có 3 lần số 3, lúc này nếu mẫu số phân tích mà số 3 xuất hiện chỉ $\le 3$ lần thì ok triệt tiêu được, còn nếu số 3 xuất hiện $> 3$ lần thì không triệt tiêu được. Nói cách khác ta chỉ cần đếm số mũ của từng số nguyên tố ở tử và ở mẫu rồi so sánh.
Phân tích nhanh bằng sàng thừa số nguyên tố nhỏ nhất
Để ý thấy $V$ là giá trị lớn nhất trong tất cả $a_i, b_i$ tối đa chỉ là $10^6$ nên dùng sàng nguyên tố thì độ phức tạp chỉ là $O(V \log \log V)$, với $V = 10^6$ cũng chẳng sợ, yên tâm (đang tính theo C++). Ta sàng ra mảng minPrime[x] $=$ thừa số nguyên tố nhỏ nhất của $x$. Sau khi sàng xong, dùng chính cái sàng đó ta có thể phân tích 1 số ra thừa số nguyên tố chỉ trong $O(\log x)$: lấy $p = $ minPrime[x], ghi nhận $p$, rồi x /= p, lặp lại đến khi $x = 1$. Em xem thêm hướng dẫn tại bài viết Sàng nguyên tố trên VNOI Wiki nhé.
Đếm số mũ bằng mảng đánh dấu
Rồi thì tạo các mảng đánh dấu, ví dụ tạo mảng có 1000001 phần tử để chỉ số từ 0 đến 1 triệu. Mảng a: a[p] là số lần xuất hiện của thừa số nguyên tố $p$ khi phân tích tử số (các $a_i$). Ví dụ a[2] là số lần xuất hiện của 2, a[3] là số lần xuất hiện của 3. Tương tự ta có mảng b cho mẫu số.
Rồi duyệt mảng b, với những b[p] > 0 thì tính b[p] -= a[p] (triệt tiêu). Sau đó nếu b[p] > 0 mà $p$ khác 2 và 5 thì coi như vô hạn, dừng ngay quá trình duyệt. Còn nếu xét đến cuối cùng mà mọi thứ vẫn ổn thì là hữu hạn.
Minh hoạPhân tích và triệt tiêu từng bước
Em nhập dãy tử $a$ và dãy mẫu $b$ (cùng số phần tử, tối đa 8 số, mỗi số $\le 10^6$) rồi bấm Tiếp để xem từng số được phân tích, rồi các thừa số ở mẫu bị tử triệt tiêu ra sao:
CodeSàng minPrime + đếm số mũ
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ với em chứ chưa có clean đâu nha, anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> minPrime(1000001, 0);
for (int i = 2; i * i <= 1000000; ++i) {
if (minPrime[i] == 0) { //if i is prime
for (int j = i * i; j <= 1000000; j += i) {
if (minPrime[j] == 0) {
minPrime[j] = i;
}
}
}
}
for (int i = 2; i <= 1000000; ++i) {
if (minPrime[i] == 0) {
minPrime[i] = i;
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(1000001, 0);
for(int i = 0; i < n; ++i){
int x;
cin >> x;
while(x != 1){
a[minPrime[x]]++;
x /= minPrime[x];
}
}
vector<int> b(1000001, 0);
for(int i = 0; i < n; ++i){
int x;
cin >> x;
while(x != 1){
b[minPrime[x]]++;
x /= minPrime[x];
}
}
bool flag = true;
for(int i = 2; i <= 1000000; ++i){
if(b[i] != 0){
b[i] -= a[i];
if(b[i] > 0 && i != 2 && i != 5){
flag = false;
break;
}
}
}
if(flag == true){
cout << "finite\n";
}
else{
cout << "repeating\n";
}
}
return 0;
}import sys
import math
data = sys.stdin.read().split()
idx = 0
max_num = 10**6
min_prime = list(range(max_num + 1))
for i in range(2, int(math.isqrt(max_num)) + 1):
if min_prime[i] == i:
min_prime[i*i::i] = [i] * len(min_prime[i*i::i])
t = int(data[idx])
idx += 1
for _ in range(t):
n = int(data[idx])
idx += 1
a_factors = {}
for _ in range(n):
x = int(data[idx])
idx += 1
while x != 1:
p = min_prime[x]
a_factors[p] = a_factors.get(p, 0) + 1
x = x // p
b_factors = {}
for _ in range(n):
x = int(data[idx])
idx += 1
while x != 1:
p = min_prime[x]
b_factors[p] = b_factors.get(p, 0) + 1
x = x // p
flag = True
for p in b_factors:
if p != 2 and p != 5:
if b_factors[p] > a_factors.get(p, 0):
flag = False
break
print("finite" if flag else "repeating")import sys
from collections import Counter
def main():
data = sys.stdin.buffer.read().split()
M = 10 ** 6
mp = list(range(M + 1)) # mp[x] = một thừa số nguyên tố của x
for i in range(2, 1001):
if mp[i] == i:
mp[i * i::i] = [i] * len(range(i * i, M + 1, i))
t = int(data[0]); p = 1; out = []
for _ in range(t):
n = int(data[p]); p += 1
ca = Counter(map(int, data[p:p + n])) # gộp các giá trị trùng nhau
cb = Counter(map(int, data[p + n:p + 2 * n])); p += 2 * n
need = Counter() # số mũ của từng p trong mẫu
for x, c in cb.items():
while x != 1:
q = mp[x]; x //= q
if q != 2 and q != 5:
need[q] += c
if need:
for x, c in ca.items():
while x != 1:
q = mp[x]; x //= q
if q in need:
need[q] -= c
out.append('finite' if all(v <= 0 for v in need.values()) else 'repeating')
print('\n'.join(out))
main()Đánh giá độ phức tạp:
Sàng chạy một lần $O(V \log \log V)$. Mỗi bộ dữ liệu: tạo 2 mảng đếm $O(V)$, phân tích $2n$ số mỗi số $O(\log V)$ (một số $\le 10^6$ có không quá 19 thừa số nguyên tố, ví dụ $2^{19} = 524288$), duyệt mảng b $O(V)$. Với $T = 10$ thì tổng cộng cỡ $10 \cdot (2 \cdot 10^6 + 2 \cdot 10^5 \cdot 19)$ $\approx 6 \cdot 10^7$ phép tính, thoải mái trong 1 giây.
Ghi chú về bản Python của anh: dòng min_prime[i*i::i] = [i] * ... gán đè lên cả những ô đã có thừa số nhỏ hơn (ví dụ min_prime[12] lúc đầu là 2, tới $i = 3$ bị đè thành 3), nên mảng này không hẳn là thừa số nhỏ nhất. Nhưng nó luôn là một thừa số nguyên tố của $x$, nên việc chia dần x //= p vẫn phân tích đúng, kết quả không đổi. Bản Python thứ hai mình viết thêm: gộp các giá trị trùng nhau bằng Counter và chỉ đếm những thừa số khác 2, 5 có trong mẫu, nên nhanh hơn.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét