CF 585 E Present for Vitalik the Philatelist

我们假设$f(x)$表示与$x$互质的数的个数，$s(x)$为 gcd 为$x$的集合的个数。

那么显然答案就是

$$\sum_{i > 1} f(i)s(i)$$

所以我们现在考虑怎么求$f$和$s$。

先考虑$f$，

$$f(x) = \sum_{i} [gcd(i,x) = 1] c_i\\f(x) = \sum_{i} c_i \sum_{d|gcd(i,x)} \mu(d)\\f(x) = \sum_{d | x} \mu(d) \sum_{d|i} c_i$$

我们设$t(x) = \sum_{x|i} c_i$，不难发现这就是我的 这篇博客 里面的第二种卷积，可以筛出来。

那么

$$f(x) = \sum_{d|x} \mu(d) t(d)$$

然后又可以用第一种卷积来做，于是我们就跑出了$f$。

现在考虑怎么求$s$，我们可以假设$s’(x)$就是 gcd 为$x$的倍数的所有集合的个数。我们需要算出$x$的倍数的数字个数，就是$\sum_{x|i} c_i$，这个不就是前面的$t(x)$吗！

所以显然有

$$s'(x) = 2^{t(x)} - 1$$

同时我们知道

$$s'(x) = \sum_{x|d} s(d)$$

这个东西就是第二个卷积的反过来的形式，也就是第四种卷积！

所以我们可以三次$O(w\log\log w)$跑过去啦。

开始看错$w$大小了。。MLE了两发。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "queue"
using namespace std;
#define MAXN 10000006
#define P 1000000007
int n;
int A[500006] , c[MAXN] , _[500006] , mu[MAXN] , s[MAXN];
int pri[MAXN] , en , lim;
void sieve( int x ) {
    pri[0] = 1; mu[1] = 1;
    for( int i = 2 ; i <= x ; ++ i ) {
        if( !pri[i] ) pri[++ en] = i , mu[i] = -1;
        for( int j = 1 ; i * pri[j] <= x && j <= en ; ++ j ) {
            pri[i * pri[j]] = 1;
            if( i % pri[j] == 0 ) { mu[i * pri[j]] = 0; break; }
            mu[i * pri[j]] = -mu[i];
        }
    }
}
signed main() {
//    freopen("in","r",stdin);
    cin >> n;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , ++ c[A[i]] , lim = max( lim , A[i] );
    sieve( lim );
    for( int i = 1 ; i <= en ; ++ i )
        for( int j = lim / pri[i] ; j ; -- j )
            c[j] += c[j * pri[i]];
    for( int i = 1 ; i <= lim ; ++ i ) mu[i] *= c[i];
    for( int i = 1 ; i <= en ; ++ i )
        for( int j = 1 ; j * pri[i] <= lim ; ++ j )
            ( mu[j * pri[i]] += mu[j] ) %= P;
    _[0] = 1;for( int i = 1 ; i < 500006 ; ++ i ) _[i] = _[i - 1] * 2 % P;
    for( int i = 1 ; i <= lim ; ++ i ) s[i] = _[c[i]] - 1;
    for( int i = en ; i ; -- i )
        for( int j = 1 ; j * pri[i] <= lim ; ++ j )
            ( s[j] -= s[j * pri[i]] ) %= P;
    int ans = 0;
    for( int i = 2 ; i <= lim ; ++ i ) ( ans += 1ll * s[i] * mu[i] % P ) %= P;
    cout << ( ans + P ) % P << endl;
}