There are several test cases.
Each test start with positive integers N(1 ≤ N ≤ 100),which means there are N extraterrestrials on the alien planet.?
The following N lines,each line contains a positive integer pi ( 2 ≤ pi ≤10^18),indicate the i-th extraterrestrial is born with pi number.
The input will finish with the end of file.
For each the case,your program will output maximum number of friend pair.
Sample Input
3
2
2
3
4
2
5
3
8
Sample Output
1
2
HINT
当遇到匹配问题时,而且只能用一次,这时应想一下二分最大匹配。
#include<stdio.h>
#include<math.h>
#include <algorithm>
#include<string.h>
#include <time.h>
using namespace std;
#define ll long long
//-----大素数的判断-------
ll mult_mod(ll a,ll b,ll n)
{
ll s=0;
while(b)
{
if(b&1) s=(s+a)%n;
a=(a+a)%n;
b>>=1;
}
return s;
}
ll pow_mod(ll a,ll n)
{
ll s=1;
while(b)
{
if(b&1) s=mult_mod(s,a,n);
a=mult_mod(a,n);
b>>=1;
}
return s;
}
int Prime(ll n)
{
ll u=n-1,pre,x;
int i,j,k=0;
if(n==2||n==3||n==5||n==7||n==11) return 1;
if(n==1||(!(n%2))||(!(n%3))||(!(n%5))||(!(n%7))||(!(n%11))) return 0;
for(;!(u&1);k++,u>>=1);
srand((ll)time(0));
for(i=0;i<5;i++)
{
x=rand()%(n-2)+2;
x=pow_mod(x,u,n);
pre=x;
for(j=0;j<k;j++)
{
x=mult_mod(x,x,n);
if(x==1&&pre!=1&&pre!=(n-1))
return 0;
pre=x;
}
if(x!=1) return 0;
}
return 1;
}
int n,ok[105][105],mark[105],vist[105];
int DFS(int x)
{
for(int i=1;i<=n;i++)
if(ok[x][i]&&vist[i]==0)
{
vist[i]=1;
if(mark[i]==0||DFS(mark[i]))
{
mark[i]=x; return 1;
}
}
return 0;
}
int main()
{
ll a[105];
while(scanf("%d",&n)>0)
{
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
memset(ok,sizeof(ok));
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
if(Prime(a[i]+a[j]))
ok[i][j]=ok[j][i]=1;
int ans=0;
memset(mark,sizeof(mark));
for(int i=1;i<=n;i++)
{
memset(vist,sizeof(vist));
ans+=DFS(i);
}
printf("%dn",ans/2);
}
}