Codeforces Round 904 (Div. 2)

\(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");
}