GCD GCD GCD

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
dang7rickroll
Dạng bài
Ngôn ngữ cho phép
C, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Scala
Điểm: 900 Thời gian: 0.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai số nguyên dương \(X\) và \(Y\), đếm số lượng số nguyên \(K\) với \(0 \leq K < Y\) thỏa mãn \(\gcd(X,Y)=\gcd(X+K,Y)\).

Input

  • Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \leq 100\));
  • \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(X\) và \(Y\) (\(X,Y \leq 10^5\))

Output

  • Ứng với mỗi câu hỏi in ra đáp số cần tìm.

Scoring

  • Subtask 1 [\(40\%\)]: \(Y \leq 10^4\);
  • Subtask 2 [\(60\%\)] Không ràng buộc gì thêm.

Example

Test 1

Input 
1
3 15
Output 
4
Note
  • Có \(4\) giá trị \(0\), \(3\), \(6\), \(9\) thỏa mãn yêu cầu đề bài

Bình luận


  • 0
    2009_nhatminh    3:14 p.m. 30 Tháng 8, 2023

    bai nay lam kieu j v mn


    • -6
      SBD12_LamLDK    2:15 p.m. 23 Tháng 7, 2024

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • 2
        PhucDepZai    4:09 p.m. 23 Tháng 7, 2024

        code giả đấy


        • -10
          SBD12_LamLDK    5:02 p.m. 23 Tháng 7, 2024

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


          • 0
            PhucDepZai    3:52 p.m. 24 Tháng 7, 2024

            vẫn là code giả đấy


            • -6
              SBD12_LamLDK    7:27 a.m. 25 Tháng 7, 2024

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

      7 bình luận nữa