题目链接：http://acm.ecnu.edu.cn/problem/3449/
Time limit per test: 1.0 seconds
Memory limit: 256 megabytes
唐纳德是一个数学天才。有一天，他的数学老师决定为难一下他。他跟唐纳德说：「现在我们来玩一个游戏。这个游戏总共 n 轮，每一轮我都会给你一个数（第 i
轮给出的数是 a
i
）。你每次要回答一个数，是我给出的这个数的质因数，并且你说出的数不能重复。」
因为数学老师是刻意为难，所以这个游戏很有可能不可能进行到最后。但是聪明的数学老师早就已经知道这个游戏最多能进行几轮了。现在他把问题抛给了你，想看看你知不知道。
注意，1 不是质数。
Input
输入具有如下形式：
na
1
a
2
… a
n
第一行一个整数 n (1≤n≤3 000
)。
第二行 n 个整数用空格隔开，a
1
,a
2
,…,a
n
(2≤a
i
≤10
6
)。
Output
输出游戏最多能进行几轮。
Examples
Input
3 7 6 3
Output
3
Input
5 2 2 2 2 2
Output
1
题解：
二分图最大匹配问题，对左边的n轮和右边的质因数连边。因为游戏必须一轮一轮进行下去，所有，当有一轮不匹配时就必须要退出了。
求质因数用质因数分解。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>using namespace std;
int n,a[3030],tot,q[3030];
int pre[1030000]; //质数最大有可能达到1e6
struct edge
{int to,next;
}e[6000000]; //边的数量可能达到6e6
int head[10000],cnt,vis[1030000];
void add_edge(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
bool match(int x)
{for(int i=head[x];i!=-1;i=e[i].next)if(!vis[e[i].to]){vis[e[i].to]=1;if(pre[e[i].to]==-1 || match(pre[e[i].to])){pre[e[i].to]=x;return true;}}return false;
}
void factor(int t)
{tot=0;int now=t;int tmp=(int)(sqrt(double(t))+1);for(int i=2;i<=tmp;i++){if(now%i==0){a[++tot]=i;}while(now%i==0){now/=i;}}if(now!=1)a[++tot]=now;
}int main()
{while(scanf("%d",&n)==1){int ans=0;memset(pre,-1,sizeof(pre));memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));cnt=-1;for(int i=1;i<=n;i++)scanf("%d",&q[i]);for(int i=1;i<=n;i++){int t=q[i];factor(t);for(int j=1;j<=tot;j++){add_edge(2*i+2,a[j]); //左边的顶点编号不能用质数}memset(vis,0,sizeof(vis));if(match(2*i+2)) //左边的顶点编号不能用质数ans++;elsebreak;}printf("%d\n",ans);}return 0;
}