GCD GCD GCD

Xem PDF
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: 1.0s 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 
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