Đếm số (THTA Vòng Chung kết)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small , zipdang04
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho ba số tự nhiên \(N, K\) và \(D\). Hãy đếm xem có bao nhiêu số tự nhiên \(A\) thoả mãn:

  • \(1 \le A \le N\);
  • \(A \times K\) chia hết cho \(D\).

Input

Dữ liệu nhập vào từ bàn phím gồm ba dòng:

  • Dòng đầu tiên là số tự nhiên \(N (1 \le N \le 10^{15})\).
  • Dòng thứ hai là số tự nhiên \(K (1 \le K \le N)\)
  • Dòng đầu tiên là số tự nhiên \(D (1 \le D \le 6)\).

Output

  • In ra màn hình một số duy nhất là số lượng số \(A\) thoả mãn yêu cầu đề bài.

Example

Test 1

Input 
10
4
6
Output 
3
Note

Có \(3\) số nhỏ hơn \(10\) mà nhân \(4\) chia hết cho \(6\) là: \(3, 6, 9\).

Test 2

Input 
20
5
1
Output 
20
Note

Tất cả \(20\) số từ \(1\) đến \(20\) khi nhân với \(5\) đều chia hết cho \(1\).

Bình luận


  • 0
    thuannguyen1972dn    8:05 p.m. 8 Tháng 5, 2024

    ac kieu j v mn


    • 2
      hoanganh2309hanoi    7:24 p.m. 26 Tháng 2, 2023
      Hint

      Ta có: \(A*K\) chia hết cho \(D\) khi \(\frac{A*K}{D}=A*\frac{K}{D}\) là một số nguyên.
      Trước tiên ta sẽ đưa phân số \(\frac{K}{D}\) về dạng tối giản bằng cách chia cả tử và mẫu cho ước chung lớn nhất của chúng
      Sau khi tối giản, nếu \(K \vdots D\) thì mọi số tự nhiên \(A\) thỏa mãn \(1 \le A \le N\) đều thỏa mãn nên kết quả chính là \(N\).
      Ngược lại, nếu \(K \not\vdots D\) thì ta chỉ cần tìm số các số \(A\) thỏa mãn hai điều kiện là \(1 \le A \le N\) và \(A \vdots D\)

      Reference AC Code (Python)
      Python
      from math import gcd
n = int(input())
k = int(input())
d = int(input())
k //= gcd(k,d)
d //= gcd(k,d)
if k % d == 0:
    print(n)
else:
    a = d
    b = (n // d)*d
    print((b - a)//d + 1)
      2 phản hồi

      • 0
        baonamok114    4:17 p.m. 22 Tháng 6, 2022

        ai cho em xin gợi ý của bài này không ạ?
        em làm nó toàn bị TLE