Cho dãy số gồm N số nguyên dương a1, a2, a3,…aN, và số nguyên dương K .
Hãy đếm số đoạn [i . .j ] (đảm bảo có ít nhất một phần tử), gồm các phần tử liên tiếp mà có tổng chia hết cho K , tức là ( ai+ai+1 + ⋯ +aj ) ⋮ K. Nếu không có đoạn nào có tổng chia hết cho K thì in ra số 0.
Dữ liệu vào: Đọc dữ liệu vào từ tệp input.inp
Dòng đầu là số N và số (1 ≤K≤ N≤ 106 ).
Dòng tiếp theo chứa N số nguyên a1, a2, a3,…aN các số không quá 103 .
Kết quả ra: Ghi kết quả ra tệp output.out Kết quả của bài toán
| input.inp | output.out |
| 5 2 1 2 3 4 5 |
6 Có 6 đoạn các phần tử liên tiếp chia hết cho 2 là {1,2,3}, {2}, {1,2,3,4}, {4}, {2,3,4,5}, {3,4,5} |
Code C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[100],n,sum=0, k;
cin>>n>>k;
for(int i=1;i<=n; i++){
cin>>a[i];
}
for(int i=1;i<=n; i++){
for(int j=i; j<=n; j++){
sum+=a[j];
if(sum%k==0){
cout<<"{";
for(int k=i; k<=j; k++){
cout<<k<<" ";}
cout<<"}";
}
}
sum=0;
}
}
– Kết quả:
