Hướng dẫn cho Cùng ước chung lớn nhất
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:
- Mình xin chia sẻ lời giải bài này như sau:
- Ta có: \(gcd(a,b)=gcd(a+x,b)=gcd((a+x)\text{% }b,b)\)
- Đặt \(k=(a+x)\text{% }b\implies 0\le k<b\) và ta có: \(gcd(a,b)=gcd(k,b)\)
- Đặt \(gcd(a,b)=gcd(k,b)=d\implies gcd(\frac{a}{d},\frac{b}{d})=gcd(\frac{k}{d},\frac{b}{d})=1\).
- Từ đây ta suy ra được số lượng các số \(x\) cần tìm chính bằng số lượng các số \(k\) cần tìm và chính bằng \(\phi(\frac{b}{d})\) (Vì \(gcd(\frac{k}{d},\frac{b}{d})=1\)).
- Chú ý: Vì \(0\le k,x <b\) nên ở đây ứng với mỗi giá trị của \(x\), sẽ cho 1 giá trị \(k\) và ngược lại,ứng với mỗi giá trị của \(k\), sẽ cho 1 giá trị \(x\). Nên số lượng \(x\) cần tìm , chính bằng số lượng \(k\).
- Đến đây bài toán quen thuộc: Ta chỉ việc xây dựng hàm tính phi của một số nguyên dương bất kì là xong.
- Mọi người có thể tham khảo tạ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;
}
- Các bạn có thể tham khảo lời giải bài toán tại \(\href{https://ideone.com/oUUJJF}{đây}\)
- P/s: Bạn nào chưa biết hàm phi là gì thì có thể tham khảo tại \(\href{https://vnoi.info/wiki/translate/he/Number-Theory-4.md}{đây}\)
- Nếu có gì sai hoặc khó hiểu các bạn cứ comment nhé !
Bình luận
Khi chia hai số cho ucln của chúng thì ta được hai số mới nguyên tố cùng nhau hả ... Mình hơi thắc mắc có định lí nào nói về điều này không..