银川网站建设nx110,扬州建设教育信息网站,培训机构有哪些,网站模板文件下载题目大意
给出一个长度为 n n n的序列 a i a_i ai#xff0c;要求删去若干个数#xff0c;使得剩下的数中任意两个数都不是质数。在满足条件的情况下最多能保留几个数。
有 T T T组数据。 1 ≤ T ≤ 4 , 1 ≤ n ≤ 750 , 1 ≤ a i ≤ 1 0 9 1\leq T\leq 4,1\leq n\leq 75…题目大意
给出一个长度为 n n n的序列 a i a_i ai要求删去若干个数使得剩下的数中任意两个数都不是质数。在满足条件的情况下最多能保留几个数。
有 T T T组数据。 1 ≤ T ≤ 4 , 1 ≤ n ≤ 750 , 1 ≤ a i ≤ 1 0 9 1\leq T\leq 4,1\leq n\leq 750,1\leq a_i\leq 10^9 1≤T≤4,1≤n≤750,1≤ai≤109
时间限制 2000 m s 2000ms 2000ms空间限制 512 M B 512MB 512MB 题解
首先如果一个数 k k k不是质数那一定 k k k存在一个质因数 p p p满足 p ≤ k p\leq \sqrt k p≤k 。
那么我们可以预处理出 5 × 1 0 4 5\times 10^4 5×104以内的所有质数用这些质数即可判断 2 × 1 0 9 2\times 10^9 2×109以内的每个数是不是质数。若枚举每两个数来判断是不是质数则时间复杂度是 O ( n 2 P ) O(n^2P) O(n2P)的其中 P P P为 5 × 1 0 4 5\times 10^4 5×104以内的质数个数 P 5133 P5133 P5133。
我们考虑优化。对于每个质数 p p p令 b i a i % p b_ia_i\% p biai%p然后将 b i b_i bi排序那么此时 b i b_i bi由若干个值相同的部分组成。假设有一部分的值都为 x x x则我们需要找到值都为 p − x p-x p−x的部分则枚举这两部分的 a a a值。设第一部分枚举到 a i a_i ai第二部分枚举到 a j a_j aj则如果 a i a j p a_ia_jp aiajp则 a i a j a_ia_j aiaj一定是 p p p的若干倍那么其一定是合数做一个标记。
你可能会问对于每个质数最多有可能标记 n 2 n^2 n2次那时间复杂度不还是 O ( n 2 P ) O(n^2P) O(n2P)吗
对于每个 a i a j a_ia_j aiaj它只会被它的质因数打标记而 a i a j a_ia_j aiaj的质因数最多为 log ( a i a j ) \log(a_ia_j) log(aiaj)个所以平摊下来时间复杂度为 O ( n 2 log v ) O(n^2\log v) O(n2logv)其中 v v v为 a i a j a_ia_j aiaj的最大值。枚举的时间复杂度为 O ( n P ) O(nP) O(nP)所以这部分的时间复杂度为 O ( n 2 log v n P ) O(n^2\log vnP) O(n2logvnP)。
当然也可以用用 Miller-Rabin \text{Miller-Rabin} Miller-Rabin算法来判断 a i a j a_ia_j aiaj是不是质数。
知道了每两个数之和是否为质数之后我们建一个图对于和为质数的两个数我们将这两个数在图上对应的点连一条边那么题意就是求最大点独立集。
我们观察图的性质。
如果组成的质数为偶质数那么这个质数一定为 2 2 2组成它的两个 a a a值一定都为 1 1 1。也就是说在所有 a i a_i ai中只保留最多一个 1 1 1即可保证不会出现偶质数。这个在输入的时候特殊处理一下即可。
那么 a i a j a_ia_j aiaj为质数的话只可能为奇质数那么 a i a_i ai和 a j a_j aj的奇偶性一定不同。于是上面的图就是一个二分图了。二分图的最大点独立集等于二分图的顶点数减去二分图的最大匹配数那我们只需要求这个二分图的最大匹配即可。
这个二分图的点数为 n n n边数为 m n 2 mn^2 mn2。我们可以用匈牙利算法来求二分图的最大匹配时间复杂度为 O ( n m ) O(nm) O(nm)即 O ( n 3 ) O(n^3) O(n3)。感觉会 TLE \text{TLE} TLE但是匈牙利的时间复杂度为点数乘边数。设左边的点数为 x x x则最坏情况下要做的次数为 n ⋅ x ( n − x ) n\cdot x(n-x) n⋅x(n−x)最大值为 n 3 4 \dfrac{n^3}{4} 4n3而这是跑不满的。所以用匈牙利算法是可行的。
当然也可以用 Dinic \text{Dinic} Dinic算法来求二分图的最大匹配时间复杂度为 O ( n m ) O(n\sqrt m) O(nm )即 O ( n 2 ) O(n^2) O(n2)。
求完最大匹配之后用点数减去最大匹配即可得到这个图的最大点独立集也就是答案。
时间复杂度为 O ( ∑ ( n 2 log v n P n 3 ) ) O(\sum(n^2\log vnPn^3)) O(∑(n2logvnPn3))其中 n 3 n^3 n3是带一个 1 4 \dfrac 14 41的常数的而且这跑不满时限还给了 2000 m s 2000ms 2000ms所以这是可以过的。
code
#includebits/stdc.h
using namespace std;
const int N750,P50000;
int T,n,p1,p2,q1,q2,ans,a[N5],p[P5],z[P5],gt[N5],t[N5][N5];
int tot,d[2*N*N5],l[2*N*N5],r[N5],cx[N5],cy[N5];
struct node{int x,id;
}b[N5];
bool cmp(node ax,node bx){return ax.xbx.x;
}
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void init(){for(int i2;iP;i){if(!z[i]) p[p[0]]i;for(int j1;jp[0]i*p[j]P;j){z[i*p[j]]1;if(i%p[j]0) break;}}
}
int dfs(int u){for(int ir[u];i;il[i]){if(gt[d[i]]) continue;gt[d[i]]1;if(!cy[d[i]]||dfs(cy[d[i]])){cx[u]d[i];cy[d[i]]u;return 1;}}return 0;
}
int main()
{
// freopen(cooking.in,r,stdin);
// freopen(cooking.out,w,stdout);init();scanf(%d,T);while(T--){scanf(%d,n);tot0;memset(r,0,sizeof(r));memset(t,0,sizeof(t));for(int i1,bz0;in;i){scanf(%d,a[i]);if(a[i]1){if(!bz) bz1;else{--i;--n;continue;}}t[i][i]1;}for(int nw1;nwp[0];nw){for(int i1;in;i) b[i](node){a[i]%p[nw],i};sort(b1,bn1,cmp);p1p21;q1q2n;for(;p2nb[p2].x0;p2){for(int ip1;ip2;i){int w1b[i].id,w2b[p2].id;t[w1][w2]t[w2][w1]1;}}--p2;p1p21;for(;;p1p21,q1q2-1){while(p1nq11b[p1].xb[q1].x!p[nw]){if(b[p1].xb[q1].xp[nw]) p1;else --q1;}if(p1n||q11||p1q1) break;p2p1;q2q1;while(p21nb[p21].xb[p1].x) p2;while(q2-11b[q2-1].xb[q1].x) --q2;for(int ip1;ip2;i){for(int jq2;jq1;j){int w1b[i].id,w2b[j].id;if(a[w1]a[w2]p[nw]) t[w1][w2]t[w2][w1]1;}}}}for(int i1;in;i){for(int j1;jn;j){if(!t[i][j]) add(i,j);}}ansn;memset(cx,0,sizeof(cx));memset(cy,0,sizeof(cy));for(int i1;in;i){if(a[i]%20) continue;if(!cx[i]){memset(gt,0,sizeof(gt));ans-dfs(i);}}printf(%d\n,ans);}return 0;
}
