题目大意
众所周知，近亲结婚的后代患遗传病的概率会大大增加。如果某一基因按常染色体隐性遗传方式，其子女就可能因为是突变纯合子而发病。因此，近亲婚配增加了某些常染色体隐性遗传疾病的发生风险。
现在有$n$个人，每个人都有一个遗传特征值$a_i$,假设第$i$个人和$j$个人结婚，那么风险系数为$\gcd(a_i,a_j)$，法律规定只有风险系数为$1$时两个人才能结婚。
F同学开了一个婚姻介绍所，这$n$个人可能会来登记，当然也有可能登记后取消，也有可能取消后再登记。F同学的任务就是，求出当前所有登记的人中，有多少对人是可以结婚的。
刚开始所有人都没有登记。
为出题需要，不考虑性别，基因突变和染色体变异等QAQ。
题目分析
这不是和这道题一模一样吗，双倍经验。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005,maxw=500005;
int n,m,a[maxn],u[maxw],sum[maxw];
bool Hash[maxw],bj[maxn];
vector<int>vec[maxw];
long long ans=0;
void Solve(int n) {
u[1]=1;
for(int i=1; i<=n; i++) {
if(Hash[i])vec[i].push_back(i);
for(int j=2*i; j<=n; j+=i) {
u[j]-=u[i];
if(Hash[j])vec[j].push_back(i);
}
}
}
void add(int x) {
for(auto& i:vec[x]) {
ans+=u[i]*sum[i];
sum[i]++;
}
}
void del(int x) {
for(auto& i:vec[x]) {
sum[i]--;
ans-=u[i]*sum[i];
}
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int(),Hash[a[i]]=1;
Solve(500000);
for(int i=1; i<=m; i++) {
int x=Get_Int();
if(!bj[x])add(a[x]);
else del(a[x]);
bj[x]^=1;
printf("%lld\n",ans);
}
return 0;
}
|
