Codeforces

Luogu

分析

设 $dp_i$ 表示 $\gcd$ 为 $i$ 的子序列的总长度。

考虑容斥,用 $\gcd$ 为 $i$ 的倍数(包括 $i$)的子序列的总长度减去 $\gcd$ 为 $i$ 的倍数(不包括 $i$)的子序列的总长度。

先考虑第一部分。设 $s$ 为 $i$ 的倍数的个数,则第一部分的答案为

$$ \begin{aligned} &\sum_{i=1}^s{s\choose i}\times i\\ =&\sum_{i=1}^s\frac{s!\times i}{i!\times(s-i)!}\\ =&s\times\sum_{i=1}^s\frac{(s-1)!}{(i-1)!\times(s-i)!}\\ =&s\times\sum_{i=0}^{s-1}{s-1\choose i}\\ =&s\times2^{s-1} \end{aligned} $$

第二部分的答案很容易得到,为

$$ \sum_{i|d,i\neq d}dp_d $$

于是就很容易算出 $dp_i$ 了。

实现上统计 $i$ 的倍数个数时需要开一个桶而不是暴力扫一遍。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

const int N=1000000;

int n,cnt[N+10],dp[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i) ++cnt[read()];
    int ans=0;
    for (re int i=N;i>1;--i) {
        int s=0;
        for (re int j=i;j<=N;j+=i) s+=cnt[j];
        if (!s) continue;
        dp[i]=1ll*s*qpow(2,s-1)%mod;
        for (re int j=i<<1;j<=N;j+=i) dp[i]=(dp[i]-dp[j]+mod)%mod;
        ans=(ans+1ll*dp[i]*i)%mod;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 11 月 14 日 02 : 35 PM