2017 Multi-University Training Contest - 第二场 09 TrickGCD （容斥+莫比乌斯）

r囧r小猫 2022-06-11 02:36 92阅读 0赞

题目链接：  
[HDU 6053][]

题意：  
给出你一个长度为n 的A 数组，让你构造出一个长度也为n 的B 数组，且B 数组要满足对于所有的1<=i<=n,A\[i\]<=B\[i\] ，且对于B 数组，任意一个区间的gcd>=2 ，求满足的方案数。

题解：  
容斥原理+莫比乌斯函数。  
答案就是∑ min(A) i=2 −mu(i)∗(∏ n i=1 ⌊A i k ⌋) 。  
对于f(k) 那么任意B 都应该含有k 这个因子。  
那么B i  可选择的方案数就是⌊A i k ⌋ .  
根据乘法原理：  
f(k)=∏ n i=1 ⌊A i k ⌋ 。

因为gcd(1,n)>=2 ，那么我们可以考虑分别计算gcd 是2 的倍数，gcd 是3 的倍数…gcd 是k （k 为质数）的倍数。然后相加，但这样会有重复，所以我们只要在系数上乘上一个莫比乌斯函数就可以了。然后，如果直接枚举每一个质数为作gcd ，肯定会T ，O(n 2 ) 。我们可以考虑预处理A 数组中每个数的个数并做前缀和，然后再O(nlogn) 枚举A i k  。

设cnt\[a\] 是A 中A\[i\]<=a 的元素个数，求一下前缀和即可。  
因为A 中⌊A i k ⌋=t 的所有的元素个数为：  
cnt\[(t\+1)k−1\]−cnt\[tk−1\] 。  
那么，那么A 中与k 的商等于t  的元素对f(k) 的贡献为:  
t cnt\[(t\+1)k−1\]−cnt\[tk−1\]  。  
总复杂度O(nlognlogn) 。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int mod=1e9+7;
    typedef long long ll;
    
    int mu[100005];
    
    void mobius(int n)
    {
        mu[1]=1;
        for(int i=1;i<=n;i++){
            for(int j=i+i;j<=n;j+=i){
                mu[j] -= mu[i];
            }
        }
    }
    int cnt[200005];
    ll ans;
    ll q_mod(ll x,int y)
    {
        ll res=1;
        while(y)
        {
            if(y&1){
                res = res * x % mod;
            }
            y >>= 1;
            x = x * x % mod;
    
        }
        return res;
    }
    
    int main()
    {
        int cas = 0;
        int n,t,Min;
        mobius(100000);
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            Min=100000;
            for(int i=0;i<=200000;i++) cnt[i]=0;
            while(n--)
            {
                int x;
                scanf("%d",&x);
                cnt[x]++;
                Min=min(Min,x);
            }
            ll ans=0;
            for(int i=1;i<=200000;i++)
            {
                cnt[i]+=cnt[i-1];
            }
            for(int i=2;i<=Min;i++)
            {
                ll temp=1;
                for(int j=1;i*j<=100000;j++)
                {
                    temp=(temp * q_mod(1LL*j,cnt[i*j+i-1]-cnt[i*j-1]))%mod;
                }   
                ans=(ans-temp*mu[i]+mod)%mod;
            }
            printf("Case #%d: ",++cas);
            printf("%lld\n",ans);
        }
        return 0;
    }

[HDU 6053]: http://acm.hdu.edu.cn/showproblem.php?pid=6053