#include <iostream>
#include <vector>

using namespace std;

vector<int> primeFactors(int n) {
    vector<int> factors;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> factors = primeFactors(k);
    int sum = accumulate(a.begin(), a.end(), 0);
    vector<vector<bool>> dp(n+1, vector<bool>(sum+1, false));
    dp[0][0] = true;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= sum; ++j) {
            dp[i][j] = dp[i-1][j];
            if (j >= a[i-1]) {
                for (int factor : factors) {
                    if (a[i-1] % factor == 0) {
                        dp[i][j] = dp[i][j] || dp[i-1][j-a[i-1]];
                        break;
                    }
                }
            }
        }
    }

    for (int j = 0; j <= sum; ++j) {
        if (dp[n][j]) {
            cout << j << endl;
            break;
        }
    }

    return 0;
}

`k^2-k+10`

`=(k-1/2)^2+9,75>9`

`k^2-k+10` là số chính phương nên đặt

`k^2-k+10=a^2(a>3,a in N)`

`<=>4k^2-4k+40=4a^2`

`<=>(2k-1)^2+39=4a^2`

`<=>(2k-1-2a)(2k-1+2a)=-39`

`=>2k-2a-1,2k+2a-1 in Ư(39)={+-1,+-3,+-13,+-39}`

`2k+2a>6`

`=>2k+2a-1> 5`

`=>2k+2a-1=39,2k-2a-1=-1`

`=>2k+2a=40,2k-2a=0`

`=>a=k,4k=40`

`=>k=10`

Vậy `k=10` thì `k^2-k+10` là SCP

`+)2k+2a-1=13,2k-2a-1=-3`

`=>2k+2a=14,2k-2a=-2`

`=>k+a=7,k-a=-1`

`=>k=3`

Vậy `k=3` hoặc `k=10` thì ..........

t ko bt lm, ms k10

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.

#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;
}

#include <bits/stdc++.h>

using namespace std;

long long x,i,n,nn;

int main()

{

cin>>n;

int dem=0;

for (i=1; i<=n; i++)

{

cin>>x;

if (x==0) dem++;

}

cout<<dem;

return 0;

}

Input:N nguyên dương ,dãy A gồm N số nguyên A1,A2,...An, số nguyên k

Output:- số lg các số bằng 0 trong dãy

- slg các số chẵn trong dãy

Tổng các số là bội của k trong dãy 

- số lg các số các số bằng k tong dãy

+minh hoạ: N=8

....

Lời giải:

Sử dụng bổ đề: Một số chính phương $x^2$ khi chia 3 dư 0 hoặc 1.

Chứng minh:

Nêú $x$ chia hết cho $3$ thì $x^2\vdots 3$ (dư $0$)

Nếu $x$ không chia hết cho $3$. Khi đó $x=3k\pm 1$ 

$\Rightarrow x^2=(3k\pm 1)^2=9k^2\pm 6k+1$ chia $3$ dư $1$

Vậy ta có đpcm

-----------------------------

Áp dụng vào bài:

TH1: Nếu $a,b$ chia hết cho $3$ thì hiển nhiên $ab(a^2+2)(b^2+2)\vdots 9$

TH1: Nếu $a\vdots 3, b\not\vdots 3$

$\Rightarrow b^2$ chia $3$ dư $1$

$\Rightarrow b^2+3\vdots 3$

$\Rightarrow a(b^2+3)\vdots 9$

$\Rightarrow ab(a^2+3)(b^2+3)\vdots 9$

TH3: Nếu $a\not\vdots 3; b\vdots 3$

$\Rightarrow a^2$ chia $3$ dư $1$

$\Rightarrow a^2+2\vdots 3$

$\Rightarrow b(a^2+2)\vdots 9$

$\Rightarrow ab(a^2+2)(b^2+2)\vdots 9$

TH4: Nếu $a\not\vdots 3; b\not\vdots 3$

$\Rightarrow a^2, b^2$ chia $3$ dư $1$

$\Rightarrow a^2+2\vdots 3; b^2+2\vdots 3$

$\Rightarrow ab(a^2+2)(b^2+2)\vdots 9$

Từ các TH trên ta có đpcm.