Question

Cho dãy số nguyên gồm n phần tử a1,a2,...,an và số nguyên dương k.Yêu cầu: Hãy xác định số lượng các đoạn con có tổng các phần tử chia hết cho k.Dữ liệu: vào từ file DIVK.INP.- Dòng đầu là 2 số nguyên dương n và k (n≤104; k≤9).- Trong n dòng sau, dòn...

Answer 1

const fi='divk.inp'

fo='divk.out'

var f1,f2:text;

a:array[1..100]of integer;

i,n,k,dem,j,x,t:integer;

begin

assign(f1,fi); reset(f1);

assign(f2,fo); rewrite(f2);

readln(f1,n,k);

for i:=1 to n do 

  read(f1,a[i]);

dem:=0;

for i:=1 to n do 

  for j:=1 to n do 

begin

if i<j then 

begin

t:=0;

for x:=i to j do 

  t:=t+a[x];

if t=k then inc(dem);

end;

for i:=1 to n do 

  if k=a[i] then inc(dem);

writeln(f2,dem);

close(f1);

close(f2);

end.

Answer 2

#include <bits/stdc++.h>
using namespace std;
#define nhungcute ios_base::sync_with_stdio; cin.tie(0); cout.tie(0);
const int N=1500;
long long n,k,a[N],i,j,c[N][101];
int main(){
nhungcute
    cin>>n>>k;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++){
        a[i]=a[i]%k;
    }
    for(i=1;i<k;i++)
    c[1][i] =-1e9;
    c[1][a[0]]=0;
    c[1][a[1]]=1;
    for(i=2;i<=n;i++){
        for(j=0;j<k;j++){
        c[i][j]=max(c[i-1][j],c[i-1][(j-a[i]+k)%k]+1);
        }
    }
    cout<<c[n][0];
    return 0;
}