\(A. Simple Design\)
https://codeforces.com/contest/1884/submission/233628914
\(B. Haunted House\)
https://codeforces.com/contest/1884/submission/233629446
\(C. Medium Design\)
https://codeforces.com/contest/1884/submission/233632930
\(D. Counting Rhyme\)
题意：给定长度为 \(n\) 的数组 \(a\) 。寻找对 \((i,j),1\le i< j\le n\) ，使得 \(a[i]%a[k]==0\) 与 \(a[j]%a[k]==0\) 不同时发生，其中 \(1\le k\le n\) 。求这样的对的数量。
解法：显然的，一个 \(pair\) 满足上面的条件等同于 \(gcd(a[i],a[j])\) 的约数不在数组中。那么不妨用数组内的数字去倍数铺满整个 \(1-n\) 的值域，这样没有被铺到的地方是合法的 \(gcd(a[i],a[j])\) 的值。我们再用 \(dp[i]\) 表示 \(gcd(a[i],a[j])==i\) 的对数，具体的是 \(n*(n-1)/2\) ,其中 \(n\) 为以 \(i\) 为倍数的数字个数，但 \(n*(n-1)/2\) 中还包括了以 \(2i,3i,…\) 为 \(gcd\) 的答案需要减掉。那么这样答案就是没有被铺到的 \(dp\) 值的和。
这样的 \(dp\) 方式见过好几次，但是都不太能自己写出来，不知道是我理解的不够还是做的类似的题太少。需要类似题目的题单。
void solve(){
int n=read();
vector<int>a(n+1),cnt(n+1),f(n+1),vis(n+1);
for(int i=1;i<=n;i++){
a[i]=read();
vis[a[i]]=1;
cnt[a[i]]++;
}
for(int i=n;i>=1;i--){
int tmp=0;
for(int j=i;j<=n;j+=i){
vis[j]|=vis[i];
tmp+=cnt[j];
}
f[i]=tmp*(tmp-1)/2;
for(int j=2*i;j<=n;j+=i){
f[i]-=f[j];
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
ans+=f[i];
}
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}