Hướng dẫn cho Phân số tối giản (TS10 LQĐ, Đà Nẵng 2019)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
- Thấy nhiều bạn bình luận trong nhóm chat sôi nổi quá, mình xin chia sẻ lời giải của bài này như sau
- Về mặt ý tưởng của thuật toán: Thì đây là bài tính phi của một số nguyên dương \(n\) bình thường (Vì \(\phi(n)\) chính là số các số nguyên tố cùng nhau với \(n\)).
- Nút thắt của bài toán này là vấn đề thời gian (khá chặt)
- Dưới đây mình sẽ đưa ra hai solution
- Một cái bị TLE ở test 100, và một test đã AC
- Đầu tiên nói về ý tưởng code:
- Để xây dựng hàm phi một cách thông minh, ta có một nhận xét sau:
- Đó là, nếu \(p\) là số nguyên tố thì \(\phi(p)=p-1\). Mình sẽ tận dụng cái này để xử lý trong trường hợp \(n\) lớn.
- Khi đó đầu tiên ta sẽ kiểm tra \(n\) có phải là số nguyên tố hay không, nếu có thì ta in ra \(n-1\), ngược lại ta in ra \(phi(n)\), trong đó hàm \(phi(n)\) được thực hiện như dưới đây:
ll phi(ll n){
ll ans = n;
ll d = 2,dem;
while(d*d<=n){
dem = 0;
while(n%d==0){
n/=d;
dem++;
}
if(dem>0) ans-=ans/d;
d++;
}
if(n>1) ans-=ans/n;
return ans;
}
- Giờ nút thắt chính đó là làm sao để ta kiểm tra với một số có phải là số nguyên tố hay không ? (Với \(n\) lớn , \(n\sim 1e16\))
- Dưới đây là hai version: Version 1 cho TLE (test 100), Version 2 cho AC
- Version 1: TLE
ll check(ll n){
if(n==1) return 0;
if(n==2||n==3) return 1;
for(ll i=2;i<=(ll)sqrt(n);i++){
if(n%i==0) return 0;
}
return 1;
}
- Version 2: AC
ll check(ll n){
if(n<=1) return 0;
if(n<=3) return 1;
if(n%2==0||n%3==0) return 0;
for(ll i=5;i*i<=n;i+=6)
if(n%i==0||n%(i+2)==0)
return 0;
return 1;
}
- Rõ ràng điểm khác biệt giữa hai version này chỉ là step ở vòng for (version 1: \(O(\sqrt{n})\), version 2: \(O(\frac{\sqrt{n}}{6})\)), và đến đây nút thắt đã giải quyết !!!!!
- Từ đây ta rút ra một kinh nghiệm khi check một số có phải là số nguyên tố hay không, ta nên dùng version 2.
-
Như vậy là bài toán đã được giải quyết hoàn tất, nếu có gì sai hoặc khó hiểu, các bạn cứ comment !
-
Các bạn có thể tham khảo code tại \(\href{https://ideone.com/wml4Gn}{đây}\)
Bình luận (1)