1552: Friends
Submit Page Summary Time Limit: 3 Sec Memory Limit: 256 Mb Submitted: 837 Solved: 236
On an alien planet, every extraterrestrial is born with a number. If the sum of two numbers is a prime number, then two extraterrestrials can be friends. But every extraterrestrial can only has at most one friend. You are given all number of the extraterrestrials, please determining the maximum number of friend pair.
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.
题意很简单，每个人有一个编号，如果两个人的编号之和是一个质数，那么两个人可以交朋友，然后每个人最多有一个朋友，问最多能够组成多少个朋友对。
很裸的一个二分图匹配，但是问题就是编号可以很大，大到1e18，那么主要问题就是判断一个大数字n，是否是质数。那么这个该怎么做呢？Miller_Rabins素数测试。
首先回顾一下，在此之前，我们用的判断素数的方法是试除法，即对于每一个数字n，从2开始到n-1，看这些数字能否整除n。这样时间复杂度是O(N)的，那么如果要求素数复杂度就是O(N^2)。紧接着，我们又学了筛法求素数，然后还有线性欧拉筛，这样求素数的复杂度可以优化到O(N)，但是即便如此，我们也不可能求出1e18那么大的素数，时间复杂度和空间都不允许。所以得借助一些工具。
还是用的Fermat小定理。如果n是质数且n不为2，那么a^(n-1)≡1(mod n)。然后根据推倒，对于满足Fermat小定理的n，把n-1分解为(2^r)*s，那么a^r≡1(mod n)或者对于所有的1<=j<=s都满足a^(2*j*r)≡n-1(mod n)。意思是，如果n为奇质数，对于任意与它互质的数字a，都有上面的结论。可以看出这是一个必要条件，满足了必要条件不一定就能确定某一个数字是否是质数。但是，如果我进行多次测试，使用不同的a呢？这样我就可以大大的减少错误的可能。通常来说，取随机的a，测试10次如果都通过，那么这个数字就是质数。然后时间复杂度，这个就很快了，最坏情况为O(klogN)其中k为测试次数。
这题就是枚举任意两点，如果两点之和为质数，那么连边，最后跑一边最大匹配即可。具体见代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<time.h> #define LL long long #define N 110 using namespace std; namespace Miller_Rabin { LL multiply(LL a,LL b,LL mod) { LL res=0; while(b) { if(b&1) res=(res+a)%mod; b>>=1;a=(a+a)%mod; } return res; } LL qpow(LL a,LL b,LL mod) { LL res=1; while(b) { if (b&1) res=multiply(res,a,mod); b>>=1; a=multiply(a,a,mod); } return res; } bool check(int a,LL n,LL r,int s) { LL x=qpow(a,r,n);if (x==1||x==n-1) return 1; //若可以用__int128则用，如此则不需要重载乘法 while (s--) {x=multiply(x,x,n);if(x==n-1)return 1;} return 0; } bool isprime(LL n) { if (n==2) return 1; if (n<1||n&1==0) return 0; LL r=n-1; int s=0; while(n&1==0) r>>=1,s++; for(int i=1;i<=5;i++) { int a=rand()%(n-1)+1; if (!check(a,n,r,s)) return 0; } return 1; } } bool cover[N],mp[N][N]; int link[N],n; LL a[N]; bool find(int i) { for(int k=1;k<=n;k++) if (!cover[k]&&mp[i][k]) { cover[k]=1; if (find(link[k])||link[k]==0){link[k]=i;return 1;} } return 0; } int hungry() { int res=0; for(int i=1;i<=n;i++) { memset(cover,0,sizeof(cover)); if (find(i)) res++; } return res; } int main() { srand(time(0)); while(~scanf("%d",&n)) { memset(mp,0,sizeof(mp)); memset(link,0,sizeof(link)); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if (Miller_Rabin::isprime(a[i]+a[j])) mp[i][j]=mp[j][i]=1; printf("%d\n",hungry()/2); } return 0; }
