« CÂU HỎI
Tin Học · Lớp $10$
Cho dãy số nguyên $a1,a2,…,an$ và số nguyên dương $k.$ Hãy đếm số lượng đoạn con liên tiếp có tổng chia hết cho $k.$ ( Giải bằng Python )

Question

Khanh · Accepted Answer

{"userId":5433079,"userName":"Minhthu008"}

# nhập dữ liệu

a = list(map(int, input().split()))

k = int(input())

n = len(a)

dem = 0

#đếm số lượng đoạn con thỏa mãn

for i in range(n):

tong = 0

for j in range(i, n):

tong += a[j]

if tong % k == 0:

dem += 1

print(dem)

Timi · Answer

Để giải bài toán đếm số lượng đoạn con liên tiếp có tổng chia hết cho k, ta có thể sử dụng kỹ thuật prefix sum và modulo.

Ý tưởng:
- Tính prefix sum: prefix[i] = tổng a1 + a2 + ... + ai
- Đoạn con từ i đến j có tổng chia hết cho k khi và chỉ khi (prefix[j] - prefix[i-1]) % k == 0
- Tương đương prefix[j] % k == prefix[i-1] % k
- Vậy ta chỉ cần đếm số cặp i, j sao cho prefix[i] % k bằng nhau.

Cách làm:
- Tính prefix sum modulo k
- Dùng dictionary để đếm số lần xuất hiện mỗi giá trị modulo
- Với mỗi giá trị modulo xuất hiện t lần, số đoạn con tương ứng là t*(t-1)/2 (chọn 2 vị trí làm đầu và cuối)
- Cộng thêm số đoạn con bắt đầu từ đầu (prefix sum = 0)

Dưới đây là code Python minh họa:

```python
def count_subarrays_divisible_by_k(arr, k):
    prefix_mod_count = {0: 1}  # prefix sum mod k và số lần xuất hiện
    prefix_sum = 0
    result = 0

for num in arr:
        prefix_sum += num
        mod = prefix_sum % k
        if mod in prefix_mod_count:
            result += prefix_mod_count[mod]
            prefix_mod_count[mod] += 1
        else:
            prefix_mod_count[mod] = 1

return result

# Ví dụ sử dụng
a = [2, 3, 1, 6, 4]
k = 3
print(count_subarrays_divisible_by_k(a, k))  # Output: số đoạn con có tổng chia hết cho k
```

Bạn có thể thay đổi mảng `a` và số `k` để kiểm tra với dữ liệu khác. Nếu cần mình có thể giải thích chi tiết hơn.

๖ۣۜƝƘ♡★✞๖ۣۜ²⁴ʱღ•๖βé ʂóίβɑβɣ♡ ☪ùทջ ɦọ☪ ϑ¡ệท á☪ Ҩųỷ · Answer

#include <bits/stdc++.h>

using namespace std;

int main()
{
long long n,k,a[100005],d[100005];
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
d[0]=0;
for(int i=1;i<=n;i++) d[i]=d[i-1]+a[i];
long long nmax=-1e18;
for(int i=k+1;i<=n;i++)
{
nmax=max(nmax,d[i]-d[i-k]);
}
cout<<nmax;
}

Quỳnh Anh · Answer

{"userId":5433079,"userName":"Minhthu008"}

Phân tích thuật toán

Để giải bài toán này một cách hiệu quả (độ phức tạp $O(n)$), chúng ta sử dụng phương pháp Tổng tiền tố (Prefix Sum) và Mảng băm/Tần suất dư:

1. Một đoạn con từ vị trí $i$ đến $j$ có tổng chia hết cho $k$ khi và chỉ khi tổng tiền tố tại $j$ và tổng tiền tố tại $i-1$ có cùng số dư khi chia cho $k$.

2. Ta duyệt qua dãy số, tính tổng tích lũy và lưu lại số lượng các số dư đã xuất hiện.

________________________________________

Mã nguồn Python

python

def count_subarrays_divisible_by_k(arr, k):

# Dictionary để lưu tần suất xuất hiện của các số dư

# Khởi tạo {0: 1} vì tổng bằng 0 mặc định chia hết cho k

remainder_counts = {0: 1}

current_sum = 0

count = 0

for x in arr:

current_sum += x

# Tính số dư của tổng tiền tố cho k

remainder = current_sum % k

# Nếu số dư này đã từng xuất hiện, cộng số lần xuất hiện vào kết quả

if remainder in remainder_counts:

count += remainder_counts[remainder]

remainder_counts[remainder] += 1

else:

remainder_counts[remainder] = 1

return count

# Ví dụ sử dụng:

# n = int(input("Nhập số lượng phần tử n: "))

# a = list(map(int, input("Nhập dãy số: ").split()))

# k = int(input("Nhập số nguyên dương k: "))

a = [4, 5, 0, -2, -3, 1]

k = 5

print(f"Số lượng đoạn con có tổng chia hết cho {k} là: {count_subarrays_divisible_by_k(a, k)}")

Use code with caution.

Giải thích:

• current_sum % k: Tìm số dư của tổng từ đầu đến vị trí hiện tại.

• remainder_counts: Lưu trữ số lần mỗi số dư xuất hiện. Nếu một số dư $r$ xuất hiện $m$ lần trước đó, điều đó có nghĩa là có $m$ đoạn con kết thúc tại vị trí hiện tại có tổng chia hết cho $k$.

• Độ phức tạp: $O(n)$, tối ưu hơn rất nhiều so với cách duyệt lồng nhau $O(n^2)$.

« CÂU HỎI Tin Học · Lớp $10$ Cho dãy số nguyên $a1,a2,…,an$ và số nguyên dương $k.$ Hãy đếm số lượng đoạn con liên tiếp có tổng chia hết cho $k.$ ( Giải bằng Python )