Ami có thể đếm xem có bao nhiêu số tự nhiên từ 1 đến n chia hết cho k. Bạn có làm được như Ami không ? Hãy thử xem ! Input Dòng đầu gồm 2 số nguyên dương n và k (n , k <= 1018). Output Hãy in ra một số nguyên là kết quá của bài toán. Ví dụ Input 5 1 Output 5 Input 10 3 Output 3
2 câu trả lời
Ý tưởng + Chứng minh:
Ta chia n ra làm n/k phần.
Ví dụ (n=16; k=3) chia 16 làm 5 (16/3=5) phần
Phần 1: 1 2 3
Phần 2: 4 5 6
Phần 2: 7 8 9
Phần 2: 10 11 12
Phần 2: 13 14 5
Số 16 dư ra: bỏ.
⇒ Ta nhận thấy phần tử cuối của mỗi phần là bội của k.
⇒ Số phần chính là số số tự nhiên từ 1 đến n chia hết cho k.
⇒ Đáp án là n/k
Accepted code:
var n,k:qword;
begin
read(n,k);
write(n div k);
end.
* Ý tưởng :
- Khởi tạo biến dem = 0
- Với i lần lượt từ 1 đến n
- Nếu i chia hết cho k thì tăng giá trị biến dem lên 1 đơn vị
* Chứng minh :
- Input : 5 1
- i chạy từ 1 đến 5
+ i = 1 mod 1 = 0 ⇒ dem = 0 + 1 = 1
+ i = 2 mod 1 = 0 ⇒ dem = 1 + 1 = 2
+ i = 3 mod 1 = 0 ⇒ dem = 2 + 1 = 3
+ i = 4 mod 1 = 0 ⇒ dem = 3 + 1 = 4
+ i = 5 mod 1 = 0 ⇒ dem = 4 + 1 = 5
=> Giá trị dem = 5
* Viết chương trình :
uses crt;
var dem, n, k, i : integer;
begin
clrscr;
write('nhap so nguyen n va k : '); readln(n, k);
dem := 0;
while k > 1018 do
begin
write('nhap lai k : '); readln(k);
end;
for i := 1 to n do
if i mod k = 0 then dem := dem + 1;
write(dem);
readln
end.
