Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 111;
const int V = 69999;
const int INF = 0x3f3f3f3f;

int a[N];
int dp[V];

int gcd(int a, int b) {
    while (b) a %= b, swap(a, b);
    return a;
}

void solve() {
    int n; cin >> n;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    vector<int> state (1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        for (int j = 0; j < state.size(); ++j) {
            int g = gcd(state[j], a[i]);
            if (dp[g] == INF) state.push_back(g);
            dp[g] = min(dp[g], dp[state[j]] + 1);
        }
    }
    int g = 0;
    for (int i = 1; i <= n; ++i) g = gcd(g, a[i]);
    int ans = INF;
    for (int i = 1; i <= g; ++i) if (g % i == 0) ans = min(ans, dp[i]);
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    int nTest; cin >> nTest;
    while (nTest--) solve();
    return 0;
}

Code mẫu của RR

{$R+,Q+}
PROGRAM RTF;
CONST
  FINP='';
  FOUT='';
  maxn=100;
TYPE
  mang=array[1..maxn] of longint;
VAR
  fi,fo:text;
  kq,n:integer;
  d:longint;
  a,b:mang;
  v:array[0..maxn] of longint;
  ok:boolean;
procedure openFiles;
begin
  assign(fi,FINP); reset(fi);
  assign(fo,FOUT); rewrite(fo);
end;
procedure closeFiles;
begin
  close(fi); close(fo);
end;
procedure readInput;
var
  i:integer;
begin
  readln(fi,n);
  for i:=1 to n do
    read(fi,a[i]);
end;
procedure writeOutput;
begin
  writeln(fo,kq);
  ok:=true;
end;
function gcd(a,b:longint):longint;
begin
  if a<b then gcd:=gcd(b,a)
  else if b=0 then gcd:=a
  else gcd:=gcd(b,a mod b);
end;
function UCLN(var a:mang; n:integer):longint;
var
  d,i:longint;
begin
  if n=1 then exit(a[1]);
  d:=a[1];
  for i:=2 to n do
    d:=gcd(a[i],d);
  UCLN:=d;
end;
procedure DFS(i,k:integer);
var
  j:integer;
begin
  if ok then exit;
  for j:=v[i-1]+1 to n-k+i do
    begin
      if ok then exit;
      v[i]:=j;
      b[i]:=a[j];
      if i<k then DFS(i+1,k)
      else if UCLN(b,k)=1 then
        begin
          writeOutput;
          exit;
        end;
    end;
end;
procedure solve;
var
  t,i,j:longint;
begin
  readln(fi,t);
  for i:=1 to t do
    begin
      readInput;
      kq:=0; ok:=false; d:=UCLN(a,n);
      v[0]:=0;
      for j:=1 to n do
        a[j]:=a[j] div d;
      repeat
        inc(kq);
        DFS(1,kq);
      until ok;
    end;
end;
BEGIN
  openFiles;
  solve;
  closeFiles;
END.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#define maxn 102

int A[maxn],B[maxn],n,t,kq,nn,UC;
bool ok;

int GCD(int a,int b)
{
    int r;
    while(b>0)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

void check()
{
     int i,UCC;
     UCC = A[B[1]];
     for(int i = 2;i<=nn;i++) UCC = GCD(UCC,A[B[i]]);
     if(UCC == UC) ok = true;
}

int thu(int i)
{
     int j;
     if(ok) return 0;
     else
     {
         for(j = B[i-1]+1;j<=n;j++)
         {
             B[i] = j;
             if(i==nn) check();
             else thu(i+1);
             if(ok) return 0;
         }
     }
}
int main()
{
    int test;
    scanf("%d",&test);
    for(int ii = 1;ii<=test;ii++)
    {
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
        scanf("%d",&A[i]);
    UC = A[1];
    for(int i = 2;i<=n;i++) UC = GCD(UC,A[i]);
    for(nn=1;nn<=n;nn++)
    {
        for(int i = 1;i<=n;i++)
            B[i] = 0;
            ok = false;
        thu(1);
        if(ok) {kq = nn;break;}
    }
    printf("%d\n",kq);
    }
    //getch();
}

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[] a, d;

    static int ucln(int a,int b) {
        if(a==0 || b==0) return a+b;
        else return ucln(b,a%b);
    }

    static void init() {
        int uc = a[0];
        for(int i=1;i<n;++i) uc = ucln(uc,a[i]);
        for(int i=0;i<n;++i) a[i] /= uc;
    }

    static void process() {
        init();

        Arrays.fill(d, 0);
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=0;i<n;++i) {
            d[a[i]] = 1;
            q.add(a[i]);
        }
        while(!q.isEmpty()) {
            int x = q.remove();
            for(int i=0;i<n;++i) {
                int tmp = ucln(x,a[i]);
                if(d[tmp]==0 || d[tmp]>d[x]+1) {
                    d[tmp] = d[x]+1;
                    q.add(tmp);
                }
            }
        }

        System.out.println(d[1]);

    }

    public static void main(String[] args) throws Exception {
        BufferedReader kb = new BufferedReader( new InputStreamReader(System.in));
        int st = Integer.parseInt(kb.readLine());
        d = new int[70001];
        for(int i=0;i<st;++i) {
            n = Integer.parseInt(kb.readLine());
            StringTokenizer stt = new StringTokenizer(kb.readLine());
            a = new int[n];
            for(int j=0;j<n;++j) a[j] = Integer.parseInt(stt.nextToken());
            Arrays.sort(a);
            process();
        }
    }
}