HDU 6053(莫比乌斯反演)

题意略。

思路：首先想到暴力去扫，这样的复杂度是n * min(ai)，对于gcd = p，对答案的贡献应该是 (a1 / p) * (a2 / p) * .... * (an / p)，得出这个贡献未必要暴力地去扫，

我们可以分桶后，再求后缀和，再作差来得到个数后，进行快速幂。比如说：我们想知道gcd = p时对答案的贡献，那么add = (c1 ^ d1) * (c2 ^ d2) *.....，其中

c1是ai / p之后得出的数，d1表示(a1 / p) * (a2 / p) * .... * (an / p)中，有多少ai / p == c1，这样我们求出所有的ci所用时间是 log(n) ，对于每一个ci，要求出

ci ^ di所用时间也是log的。把每一个 <= min(ai)统计一次，所用时间是n * logn * logn。

注意，我们在枚举p的时候，只枚举由互不相同的因子组成的p，当p内含有相同因子时，它是前种情况的子集，这里肯定有重复，可以利用莫比乌斯反演来

去重。

详见代码：

#include<bits/stdc++.h>

#define maxn 100005

//#define LOCAL

using namespace std;

typedef long long LL;

const LL mod = 1e9 + ;

bool check[maxn];

int prime[maxn],mu[maxn];

LL sum[maxn];

void mobius(){

    memset(check,false,sizeof(check));

    mu[] = ;

    int tot = ;

    for(int i = ;i < maxn;++i){

        if(!check[i]){

            prime[tot++] = i;

            mu[i] = -;

        }

        for(int j = ;j < tot;++j){

            if(i * prime[j] > maxn) break;

            check[i * prime[j]] = true;

            if(i % prime[j] == ){

                mu[i * prime[j]] = ;

                break;

            }

            else mu[i * prime[j]] = -mu[i];

        }

    }

}

LL quick_pow(LL a,LL n){

    LL ret = ;

    while(n > ){

        if(n & ){

            ret *= a;

            ret %= mod;

        }

        n = n / ;

        a = a * a % mod;

    }

    return ret;

}

int main(){

    #ifdef LOCAL

    freopen("kkk.txt","r",stdin);

    freopen("kkkout.txt","w",stdout);

    #endif

    int T,cas = ;

    mobius();

    scanf("%d",&T);

    while(T--){

        int minn = maxn,maxx = -maxn;

        int n,temp;

        scanf("%d",&n);

        memset(sum,,sizeof(sum));

        for(int i = ;i < n;++i){

            scanf("%d",&temp);

            ++sum[temp];

            minn = min(minn,temp);

            maxx = max(maxx,temp);

        }

        for(int i = maxn - ;i >= ;--i)

            sum[i] += sum[i + ];

        LL ans = ;

        for(int i = ;i <= minn;++i){

            if(mu[i] == ) continue;

            LL temp = -mu[i];

            for(int j = i;j <= maxx;j += i){

                temp = (temp * quick_pow(j / i,sum[j] - sum[min(maxx + ,j + i)]) % mod);

            }

            ans += temp;

            ans = (ans % mod + mod) % mod;

        }

        printf("Case #%d: %lld\n",cas++,ans);

    }

    return ;

}

/*

1

4

4 6 9 7

*/

巴特西

HDU 6053(莫比乌斯反演)

最新文章

热门文章