首页 > 代码库 > 1439 互质对
1439 互质对
1439 互质对
题目来源： CodeForces
基准时间限制：2 秒 空间限制：131072 KB
有n个数字，a[1],a[2],…,a[n]。有一个集合，刚开始集合为空。然后有一种操作每次向集合中加入一个数字或者删除一个数字。每次操作给出一个下标x(1 ≤ x ≤ n)，如果a[x]已经在集合中，那么就删除a[x],否则就加入a[x]。
问每次操作之后集合中互质的数字有多少对。
注意，集合中可以有重复的数字，两个数字不同当且仅当他们的下标不同。
比如a[1]=a[2]=1。那么经过两次操作1，2之后，集合之后存在两个1，里面有一对互质。
Input
单组测试数据。第一行包含两个整数n 和 q (1 ≤ n, q ≤ 2 × 10^5)。表示数字的种类和查询数目。第二行有n个以空格分开的整数a[1],a[2],…,a[n] (1 ≤ a[i] ≤ 5 × 10^5),分别表示n个数字。接下来q行，每行一个整数x(1 ≤ x ≤ n)，表示每次操作的下标。
Output
对于每一个查询，输出当前集合中互质的数字有多少对。
Input示例
样例输入15 61 2 3 4 6123451样例输入22 31 1121
Output示例
样例输出1013562样例输出2010
思路：容斥原理；求容斥每个数与其他数不互质的对数，然后sum+总的再减去不互质的即可；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<queue> 6 #include<string.h> 7 #include<set> 8 #include<map> 9 #include<math.h> 10 using namespace std; 11 typedef long long LL; 12 bool flag[600005]; 13 LL cnt[600005]; 14 int ff[600005]; 15 bool prime[600005]; 16 LL sum = 0; 17 int b[20]; 18 int bns[600005]; 19 int ans[600000]; 20 int n; 21 void slove(int x,int v); 22 int main(void) 23 { 24 int q; 25 scanf("%d %d",&n,&q); 26 memset(cnt,0,sizeof(cnt)); 27 memset(flag,0,sizeof(flag)); 28 int i,j;int cn = 0; 29 for(i = 2; i < 1000; i++) 30 { 31 if(!prime[i]) 32 { 33 for(j = i; ((LL)i*(LL)j) <= 500000; j++) 34 { 35 prime[i*j] = true; 36 } 37 } 38 } 39 for(i = 2;i < 500000; i++) 40 { 41 if(!prime[i]) 42 { 43 ans[cn++] = i; 44 } 45 } 46 for(i = 0;i < cn ;i++) 47 { 48 for(j = 1;ans[i]*j <= 500000;j++) 49 { 50 ff[ans[i]*j] = ans[i]; 51 } 52 } 53 for(i = 0; i < n; i++) 54 { 55 int x; 56 scanf("%d",&bns[i]); 57 } 58 n = 0; 59 while(q--) 60 { 61 int x; 62 scanf("%d",&x); 63 int id = x; 64 x = bns[x-1]; 65 { 66 slove(x,id); 67 } 68 printf("%lld\n",sum); 69 } 70 return 0; 71 } 72 void slove(int x,int v) 73 { 74 int fl = 0; 75 if(flag[v]) 76 { 77 flag[v]=false; 78 n--; 79 sum-=n; 80 fl = 1; 81 } 82 else 83 { 84 flag[v]=true; 85 sum += n; 86 n++; 87 }//printf("%d\n",sum); 88 int c = x; 89 int cn = 0; 90 while(c>1) 91 { 92 if(cn==0) 93 { 94 b[cn++] = ff[c]; 95 } 96 else if(b[cn-1]!=ff[c]) 97 { 98 b[cn++] = ff[c]; 99 }100 c/=ff[c];101 }102 if(fl)103 {104 int i ,j;105 for(i = 1; i < (1<<cn); i++)106 {107 int ac = 1;108 int t = 0;109 for(j = 0; j < cn; j++)110 {111 if(i&(1<<j))112 {113 t++;114 ac*=b[j];115 }116 }117 if(t%2)118 {119 cnt[ac]--;120 sum += cnt[ac];121 }122 else123 {124 cnt[ac]--;125 sum -= cnt[ac];126 }127 }128 }129 else130 {131 int i ,j;132 for(i = 1; i < (1<<cn); i++)133 {134 int ac = 1;135 int t = 0;136 for(j = 0; j < cn; j++)137 {138 if(i&(1<<j))139 {140 t++;141 ac*=b[j];142 }143 }144 if(t%2)145 {146 sum -= cnt[ac];147 cnt[ac]++;148 }149 else150 {151 sum += cnt[ac];152 cnt[ac]++;153 }154 }155 }156 }
1439 互质对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。