NOIP2023模拟1联测22 黑暗料理

联测22 黑暗料理"/>

NOIP2023模拟1联测22 黑暗料理

NOIP2023模拟1联测22 黑暗料理

题目大意

自己看

思路

• 两个数相加能够产生质数的情况就是：1+1 或者 偶数+质数

  那么 1 1 1 不能保留超过一个

• 建一个图，原点连向所有奇数点，所有偶数点连向汇点，奇数点和偶数点的和为奇数的就相连

  那么答案就是隔断原、汇两点的最小割。

• 判断质数用Miller_Rabin

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
#define LL long long 
using namespace std;
const int N = 755;
int n , a[N * N * 2] , p[5] = {2 , 3 , 5 , 7 , 11} , cnt , ans , ans1 , hd[N * N * 2] , pos1[N] , pos2[N * N * 2] , cx1 , cx2 , cx[N] , cy[N] , vis[N];
struct E {int to , nt;
} e[N * N * 4];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
bool cmp (int x , int y) { return a[x] > a[y]; }
LL ksm (LL x , LL y , LL mod) {if (!y) return 1;LL z = ksm (x , y / 2 , mod);z = z * z % mod;if (y & 1) z = z * x % mod;return z;
}
bool ck (LL x , LL y) {LL mod = x - 1 , xx;if (ksm (y , mod , x) != 1)return 0;do {xx = ksm (y , mod / 2 , x);if (xx != 1 && xx != x - 1)return 0;mod >>= 1;} while (mod % 2 == 0 && xx == 1);return 1;
}
bool mb (LL x) {if (x == 1)return 0;if (x == 2 || x == 3 || x == 5 || x == 7 || x == 11)return 1;fu (i , 0 , 4) {if (!ck (x , p[i])) return 0;}return 1;
}
bool find (int x) {int y;for (int i = hd[x] ; i ; i = e[i].nt) {y = e[i].to;if (vis[y]) continue;vis[y] = 1;if (!cy[y] || find (cy[y])) {cx[x] = y , cy[y] = x;return 1;}}return 0;
}
int main () {freopen ("cooking.in" , "r" , stdin);freopen ("cooking.out" , "w" , stdout);int T , flg;scanf ("%d" , &T);while (T --) {scanf ("%d" , &n);fu (i , 1 , n)scanf ("%d" , &a[i]);cnt = ans1 = ans = flg = cx1 = cx2 = 0;fu (i , 1 , n * n * 2) hd[i] = cx[i] = cy[i] = 0;fu (i , 1 , n) {if (a[i] & 1) {if (a[i] == 1) {if (!flg) flg = 1;else {ans1 ++;continue;}}pos1[++cx1] = i;}         elsepos2[++cx2] = i;}fu (i , 1 , cx1) {fu (j , 1 , cx2) {if (a[pos1[i]] == 51 && a[pos2[j]] == 38) {ans ++;ans --;}if (mb (a[pos1[i]] + a[pos2[j]])) {add (i , cx1 + j);// cout << a[pos1[i]] << " " << a[pos2[j]] << "\n";}}}// exit (0);fu (i , 1 , cx1) {if (cx[i]) continue;fu (j , 1 , cx2) vis[j + cx1] = 0;ans += find (i);}// cout << ans;/printf ("%d\n" , n - ans1 - ans);}return 0;
}