题目大意

给长度为 $n$ 的序列,询问有多少个子序列满足它们的 gcd 为 $1$。

题解

其实这篇博客是用来 的 (强行刷文章量)
我们设 $f(x)$ 表示 $gcd = x$ 的子序列的数量,那么可以立马启发我们设 $F(x)$ 表示 gcd 是 $x$ 的倍数的子序列数量,如果我们统计出 $cnt_i$ 表示 $i$ 和 $i$ 的倍数的数量,那么 $F(x) = 2^{cnt_x} - 1$。
又可以发现 $f(x)$ 和 $F(x)$ 满足关系 $F(x) = \sum_{d|x} f(d)$,也就有 $f(x) = \sum_{x|d} F(d)\mu(d)$,直接暴力算就可以了。。。(甚至不需要任何数论分块技巧,是一道小学组数论题)

/*
 * Author: RainAir
 * Time: 2019-08-27 21:31:06
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

int prime[MAXN],mu[MAXN],tot;
int p[MAXN];

inline void prepare(){
    mu[1] = 1;
    FOR(i,2,MAXN-1){
        if(!p[i]) prime[++tot] = i,mu[i] = -1;
        for(int j = 1;j <= tot && i*prime[j] < MAXN;++j){
            p[i*prime[j]] = true;
            if(!(i%prime[j])){
                mu[i*prime[j]] = 0;
                break;
            }
            mu[i*prime[j]] = -mu[i];
        }
    }
}

inline int qpow(int a,int n){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int a[MAXN],cnt[MAXN];
int n;

signed main(){
    scanf("%lld",&n);prepare();
    FOR(i,1,n){
        int x;scanf("%lld",&x);
        int q = std::sqrt(1.0*x);
        FOR(i,1,q){
            if(!(x%i)){
                cnt[i]++;
                if(x/i != i) cnt[x/i]++;
            }
        }
    }
    int ans = 0;
    FOR(i,1,100000) (ans = (ans+(qpow(2,cnt[i])+ha-1)%ha*mu[i]+ha)%ha);
    printf("%lld\n",ans);
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/804/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏