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

Xem PDF
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


  • 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)

    • 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