Editorial for Cùng ước chung lớn nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- 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é !
Comments