Cùng ước chung lớn nhất

Xem PDF
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Bạn được cho 2 số nguyên dương \(a, b\) \((a<b)\). Hãy tính số các số x thỏa mãn \(0\leq x <b\) và \(\gcd(a,b)=\gcd(a+x,b)\).

\(\gcd(x,y)\): Ước chung lớn nhất của \(x\) và \(y\).

Input

  • Dòng đầu tiên chứa \(t\) \((1 \leq t \leq 50)\) - số câu hỏi.
  • \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) \((1 \leq a, b \leq 10^{10})\).

Output

  • Ứng với mỗi câu hỏi in ra số \(x\) cần tìm.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \((1 \leq a, b \leq 1000)\);
  • Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

Test 1

Input 
3
4 9
5 10
42 9999999967
Output 
6
1
9999999966
Note
  • Test 1: \(x\) có thể là một trong các số \([0,1,3,4,6,7]\).
  • Test 2: \(x\) chỉ có thể là 0

Bình luận


  • 5
    jumptozero    5:55 a.m. 26 Tháng 6, 2020 ← chỉnh sửa 2
    • 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é !
    1 phản hồi