codeforces-#428-D

codeforces-#428-D

七月 08, 2020

D. Winter is here

题意

有一个序列a，对于某些k 称序列i1, i2, …, ik 是无趣的当且仅当i1 < i2 < i3 < … < ik

并且 gcd(ai1, ai2, …, aik) > 1 . 并且它的无趣值为k · gcd(ai1, a i2, …, aik) . 求所有存在的无趣序列的无趣值之和，对1e9+7取模

给出一个长度为n n<1e5 的序列a ai<1e6 找出长度为k且gcd(ai1,ai2,ai3.....aik)>1 的子序列
求∑k*gcd

题解
枚举gcd 那么由此gcd能构成的子序列 应该是由 gcd ，2gcd，3gcd….即gcd的倍数构成的
那么读入时统计各个数的个数 num[x]++
所以对于枚举到的某个gcd 它对应的子序列 是由a中出现的它的所有倍数选出1个，2个… x个
(假设最多x个)形成
同时以gcd为最大公约数的子序列对应的长度k可以是1,2,3,4,5…x;

∑k=∑len C(x,len) ,(len=1,2,3,,,,x) = x 2^ {x-1}

/ 常用组合数结论 /
那么以gcd为最大公约数的子序列对答案产生的贡献可以直接计算得到
此外还要考虑gcd=4 和gcd=2 被重复计算的情况 比如{4,8,12}的gcd=4但枚举到gcd=2时也会被计入 因此考虑容斥 对于gcd=2的子序列个数要减去gcd=4,6,8,10….2x
所以我们选择从大到小枚举gcd 同时维护一个dp数组记录以i为gcd的子序列对应的∑k

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
# include<bits/stdc++.h>

# define endl "\n"

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll num[(int)1e6+5];
ll dp[(int)1e6+6];
ll qpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        y>>=1;x=(x*x)%mod;
    }
    return ans;
}
int main(){
    int n;cin>>n;
    ll maxn=0;
    for(int i=0;i<n;i++){
        ll x;cin>>x;
        num[x]++;
        maxn=max(maxn,x);
    }
    ll ans=0;
    for(ll i=maxn;i>1;i--){
        ll x=0,sum=num[i];
        for(ll j=2*i;j<=maxn;j+=i){
            x=(x+dp[j])%mod;
            sum=(sum+num[j])%mod;
            //cout<<j;
        }
        if(!sum)continue;
        dp[i]=(mod+(sum%mod*qpow(2,sum-1)%mod)%mod-x)%mod;
        //cout<<i;
        ans=(ans+(i*dp[i])%mod)%mod;
    }
    cout<<ans<<endl;
}