首页 > 代码库 > 1678 lyk与gcd
1678 lyk与gcd
1678 lyk与gcd
基准时间限制：2 秒 空间限制：131072 KB
这天，lyk又和gcd杠上了。
它拥有一个n个数的数列，它想实现两种操作。
1：将 ai 改为b。
2：给定一个数i，求所有 gcd(i,j)=1 时的 aj 的总和。
Input
第一行两个数n，Q(1<=n,Q<=100000)。接下来一行n个数表示ai(1<=ai<=10^4)。接下来Q行，每行先读入一个数A(1<=A<=2)。若A=1，表示第一种操作，紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。若B=2，表示第二种操作，紧接着一个数i。(1<=i<=n)。
Output
对于每个询问输出一行表示答案。
Input示例
5 31 2 3 4 52 41 3 12 4
Output示例
97
思路:容斥原理；
我们用容斥将每个数的质因子，然后将其所对应的数加到表中，奇加偶减，然后分解当前的询问的数，然后可以重表中找出那些和他不互质的所对应的书数的和，然后总的减去即可。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<queue> 6 #include<string.h> 7 #include<math.h> 8 #include<map> 9 using namespace std; 10 typedef long long LL; 11 int ans[100000]; 12 bool prime[100005]; 13 LL cnt[100005]; 14 int ak[100005]; 15 int tt[200]; 16 void table(int n,int cn,int v); 17 LL ac(int n); 18 int main(void) 19 { 20 int N,Q; 21 int i,j; 22 for(i = 2; i < 1000; i++) 23 { 24 if(!prime[i]) 25 { 26 for(j = i; i*j < 100000; j++) 27 { 28 prime[i*j] = true; 29 } 30 } 31 } 32 int cn = 0; 33 for(i = 2; i < 100000; i++) 34 { 35 if(!prime[i]) 36 { 37 ans[cn++] = i; 38 } 39 } 40 scanf("%d %d",&N,&Q); 41 LL sum = 0; 42 for(i = 1; i <= N; i++) 43 { 44 scanf("%d",&ak[i]); 45 sum += ak[i]; 46 table(i,cn,1); 47 }//printf("%lld\n",sum); 48 for(i = 0; i < Q; i++) 49 { 50 int val; 51 int c; 52 scanf("%d",&val); 53 if(val == 2 ) 54 { 55 scanf("%d",&c); 56 printf("%lld\n",sum-ac(c)); 57 } 58 else 59 { 60 int x,y; 61 scanf("%d %d",&x,&y); 62 table(x,cn,0); 63 sum -= ak[x]; 64 ak[x] = y; 65 sum += ak[x]; 66 table(x,cn,1); 67 } 68 } 69 return 0; 70 } 71 void table(int n,int cn,int v) 72 { 73 int f = 0; 74 bool flag = false ; 75 int x = n; 76 int cp = 0; 77 while(x > 1) 78 { 79 while(x%ans[f]==0) 80 { 81 if(!flag) 82 { 83 flag = true; 84 tt[cp++] = ans[f]; 85 } 86 x/=ans[f]; 87 } 88 f++; 89 flag = false ; 90 if(ans[f]*ans[f]>x) 91 break; 92 } 93 if(x>1) 94 tt[cp++] = x; 95 int i,j; 96 for(i = 1; i < (1<<cp); i++) 97 { 98 int sum = 1;int t = 0; 99 for(j = 0; j < cp; j++)100 {101 if(i&(1<< j))102 {103 sum*=tt[j];104 t++;105 }106 }107 if(v)108 {109 if(t%2)cnt[sum]+=ak[n];110 else cnt[sum]-=ak[n];111 }112 else113 {114 if(t%2)cnt[sum]-=ak[n];115 else cnt[sum]+=ak[n];116 }117 }118 }119 LL ac(int n)120 {121 int f = 0;122 bool flag = false ;123 int x = n;124 int cp = 0;125 while(x > 1)126 {127 while(x%ans[f]==0)128 {129 if(!flag)130 {131 flag = true;132 tt[cp++] = ans[f];133 }134 x/=ans[f];135 }136 f++;137 flag = false ;138 if(ans[f]*ans[f]>x)139 break;140 }141 if(x>1)142 tt[cp++] = x;143 int i,j;144 LL k = 0;;145 for(i = 1; i < (1<<cp); i++)146 {147 int sum = 1;148 for(j = 0; j < cp; j++)149 {150 if(i&(1<<j))151 {152 sum *= tt[j];153 }154 }155 k += cnt[sum];156 }//printf("%lld\n",k);157 return k;158 }
1678 lyk与gcd
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。