Đế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()


    • 2
      penistone    4:23 a.m. 21 Tháng 12, 2023
      Hint

      ans=n/(LCM(x,m)/x)
      Hàm LCM là hàm lấy bội chung nhỏ nhất của 2 số


      • -6
        nguyenbaongoc130113    12:39 p.m. 26 Tháng 8, 2022

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


        • 4
          JustA    10:14 p.m. 9 Tháng 5, 2022

          || Hint
          Mình test cái hint này tí thôi các anh chị em đừng nói mình ạ :'(
          Gọi lcm là bội chung nhỏ nhất của x và m
          ta có kết quả là: res = n // (lcm // x)
          ||

          1 phản hồi

          • -32
            NghiaUwU    6:16 p.m. 11 Tháng 4, 2022

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