E - Sum of gcd of Tuples (Hard) Atcoder 162 E（容斥）

题解：这个题目看着挺吓人的，如果仔细想想的话，应该能想出来。题解还是挺好的理解的。

首先设gcd(a1,a2,a3...an)=i，那么a1~an一定是i的倍数，所以ai一共有k/i种取值。有n个数，所有就有(k/i)^n种情况。光是这样还是不行的，因为a1~an的gcd可能为j*i。所以我们要减去2*i,3*i......j*i<=k。倒着来就可以了，复杂度应该是o(nlogn)

code：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=1e5+;

const ll MOD=1e9+;

ll dp[N];

ll ksm(ll x,ll y){

    ll res=;

    while(y){

        if(y&) res=res*x%MOD;

        x=x*x%MOD;

        y>>=;

    }

    return res%MOD;

}

int main(){

    ll n,k;

    cin>>n>>k;

    ll ans=;

    for(ll i=k;i>=;i--){

        dp[i]=ksm(k/i,n);

        for(ll j=*i;j<=k;j+=i) dp[i]=(dp[i]-dp[j]+MOD)%MOD;

        ans=(ans+i*dp[i]+MOD)%MOD;

    }

    cout<<ans<<endl;

    return ;

}

巴特西

E - Sum of gcd of Tuples (Hard) Atcoder 162 E（容斥）

最新文章

热门文章