testC
输入文件:
testC.in 输出文件testC.out
时限1000ms
问题描述：
给你一组数，a1,a2,a3,⋯,an。
令：G=gcd(a1,a2,a3,⋯,an)
现在从中任意删除一些数字，设剩下的数为：al1,al2,al3,⋯,alm。
再令：g=gcd(al1,al2,al3,⋯,alm)
现要求G=g，问最多能删除多少数？
输入描述：
第一行一个数n，第二行n个数a1,a2,a3,⋯,an。
1≤n≤700
1≤ai≤10000
输出描述：
输出只有一个数，表示最多能删除多少数。
样例输入：
3
4
6 8
样例输出：
1
考场上一直在想网络流的做法，当时想出了一个转换二分图最小支配集的建图方式，而自己sb地把支配集与覆盖集搞混了：
最小支配集表示选取一个点集，使图上的所有点属于这个集合或者是与集合中的点直接相连，选取的集合最小的大小。
最小覆盖集这指的是所有覆盖边的点集。
图上或二分图上的最小支配集是NP问题！！！
正解dp,f[i]表示gcd为i时的最少选择数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define PROB "testC"
#define MAXN 110000
#define INF 0x3f3f3f3f
inline int deal(int &x,int y)
{
if (y<x)x=y;
}
int gcd(int x,int y)
{
return (y%x==)?x:gcd(y%x,x);
}
int f[MAXN];
int main()
{
freopen(PROB".in","r",stdin);
//` freopen(PROB".out","w",stdout);
int i,j,k,x,y,z;
int n;
memset(f,INF,sizeof(f));
scanf("%d",&n);
scanf("%d",&x);
f[x]=;
int t=x;
for (i=;i<n;i++)
{
scanf("%d",&x);
f[x]=;
t=gcd(t,x);
for (j=;j<;j++)
{
if (f[j]==INF)continue;
deal(f[gcd(j,x)],f[j]+);
}
}
printf("%d",n-f[t]);
return ;
}