25. （完善程序）

（数据分组）问题：给定 n 个正整数，将它们分组，使得每组中的任意两个数互质（它们的最大公约数为 1）。按照以下算法可以得到最少的组数：

第一步：将第 1 个整数分到第 1 组；

第二步：尝试将第 2 个至第 n 个整数分到已有的分组中，若能分到已有的分组中，则分到第一个符合条件的组；若不能分到已有的组，则分到新生成的组中。

经过回溯算法，可以找到最小的分组数量。

例如对“70，99，25，54，11，100”这 6 个整数分组，具体分组情况如下表所示：

【输入】

第一行为 n，表示数据的个数。

第二行为 n 个空格隔开的正整数，表示分组的数据。

【输出】

一行一个正整数，表示最小分组数量。

【样例输入】

6

70 99 25 54 11 100

【样例输出】

3

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[51];
int b[51][51];
int gcd(int m, int n){ //求最大公约数
    if(n==0) return m;
    else return _________________________;
}
void find(int i){
    if(i==n){
        if(ans>m) ans=m;
        return;
    }
    for(int k=0;k<m;k++){
        bool flag=true;
        for(int j=1;j<=b[k][0];j++)
            if(_________________________){
                flag=false;
                break;
            }
        if(flag){
            b[k][0]++;
            _________________________;
            find(i+1);
            b[k][0]--;
        }
    }
    _________________________;
    find(i+1);
    m--;
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    _________________________;
    b[0][0]=1; b[0][1]=a[0];
    find(1);
    cout<<ans<<endl;
    return 0;
}

① 处应填（ ）。

{{ select(1) }}

• gcd(m,m/n)
• gcd(m,m%n)
• gcd(n,m/n)
• gcd(n,m%n)

② 处应填（ ）。

{{ select(2) }}

• gcd(a[i],b[j][k])>1
• gcd(a[i],b[j][k])==1
• gcd(a[i],b[k][j])>1
• gcd(a[i],b[k][j])==1

③ 处应填（ ）。

{{ select(3) }}

• b[k][b[k][0]]=i;
• b[k][b[k][0]]=a[i];
• b[k][b[k][0]+1]=i;
• b[k][b[k][0]+1]=a[i];

④ 处应填（ ）。

{{ select(4) }}

• m++; b[m][0]=1; b[m][1]=i;
• m++; b[m][0]=1; b[m][1]=a[i];
• b[m][0]=1; b[m][1]=a[i]; m++;
• b[m][0]=1; b[m][1]=a[i]; m++;

⑤ 处应填（ ）。

{{ select(5) }}

• m=0; ans=n;
• m=0; ans=0;
• m=1; ans=n;
• m=1; ans=0;