定义：dp[i][j] 表示 在前i个数中，使整个gcd值为j时最少取的数个数。
则有方程： gg = gcd(a[i],j)
gg == j : 添加这个数gcd不变，不添加, dp[i][j] = dp[i-1][j]
gg != j： t添加，更新答案， dp[i][gg] = dp[i-1][j] + 1
最后答案为dp[n][g] (g为原始的所有数的gcd)
时间复杂度： O(n*max(a[i]))
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000007 int dp[][];
int a[]; int gcd(int a,int b)
{
if(!b)
return a;
return gcd(b,a%b);
} int main()
{
int n,g,i,j;
scanf("%d",&n);
g = ;
int maxi = ;
for(i=;i<=n;i++)
for(j=;j<=;j++)
dp[i][j] = Mod;
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
g = gcd(g,a[i]);
maxi = max(maxi,a[i]);
dp[i][a[i]] = ;
}
//printf("%d\n",g);
for(i=;i<=n;i++)
{
for(j=;j<=maxi;j++)
{
if(dp[i-][j] != Mod)
{
int gg = gcd(a[i],j);
if(gg == j)
dp[i][gg] = min(dp[i][gg],dp[i-][j]);
else
dp[i][gg] = min(dp[i][gg],dp[i-][j] + );
}
}
}
printf("%d\n",n-dp[n][g]);
return ;
}