Đếm số (THTB Hòa Vang 2022)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
kid2201
Dạng bài
Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(3\) số nguyên dương \(x, n, m\). Hãy đếm xem có bao nhiêu số nguyên dương \(y\) thỏa mãn:

  • \(y\le n\)
  • \(x \times y\) chia hết cho \(m\)

Yêu cầu: Cho trước \(x, n, m\), hãy lập trình tìm số lượng số \(y\) thỏa mãn.

Input

  • Một dòng chứa \(3\) số \(x, n, m ( x, n, m\le 10^{16})\).

Output

  • Một số nguyên là số lượng số nguyên \(y\) thỏa mãn yêu cầu của bài toán.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^4\).
  • Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^8\).
  • Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input 
6 13 8
Output 
3
Note

Giải thích: Có \(3\) giá trị y thỏa mãn là: \(4\); \(8\); \(12\)

Bình luận


  • 0
    tk22NguyenHuyPhuc    10:04 p.m. 14 Tháng 8, 2024

    import math

    def count_valid_y(x, n, m):
    k = x % m 

    if k == 0:
    return n  
gcd_k_m = math.gcd(k, m) 
d = m // gcd_k_m

return n // d

    def main():
    x, n, m = map(int, input().strip().split())

    result = count_valid_y(x, n, m)
print(result)

    if name == "main":
    main()

      • 4 bình luận nữa