TrickGCD HDU - 6053 [Mobius]

题意:

求存在多少个数组b,使得b[i]>=a[i] && gcd(b[1]...b[n])>=2

思路:

求出所有gcd是1倍数的方案数x
求出所有gcd是1的方案数y
ans=x-y
经过系列化简,得到
明显的Mobius但是常规做法是O*(n^2), 第二个等号后面的式子,我们可以在 O(n*sqrt(n)*logn)的时间内做出来. 其中cnt代表 x/i=j的个数,那么有x在范围 [i*j,i*j+i-1] , 先预处理前缀和,O(1)查询cnt

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll MOD=1e9+7;
const ll Seed=2333;

int mu[N], vis[N], prime[N];
int summu[N];
int tot;//用来记录prime的个数
void init(){
    mu[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!vis[i]){
            prime[tot ++] = i;
            mu[i] = -1;
        }
        for(int j = 0; j < tot && i * prime[j] < N; j ++){
            vis[i * prime[j]] = 1;
            if(i % prime[j]) mu[i * prime[j]] = -mu[i];
            else{
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
}

ll qm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans;
}

void adjust(ll &a){
    a%=MOD;
    a+=MOD;
    a%=MOD;
}

ll a[N];
ll mn=0,n,mx;
ll cnt[N],sum[N];

ll solve(){
    ll ans=0;
    for(int i=2;i<=mn;i++){
        ll FI=1;
        if(!mu[i])  continue;
        for(int j=1;j<=mx/i;j++){
            FI*=qm(j,sum[min(j*i+i-1,100000)]-sum[j*i-1]);
            adjust(FI);
        }
        ans+=-mu[i]*FI;
        adjust(ans);
    }
    return ans;
}

int ks;
int main(void){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        mn=1e18;
        mx=0;
        memset(cnt,0,sizeof cnt);
        memset(sum,0,sizeof sum);
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            cnt[a[i]]++;
            mn=min(mn,a[i]);
            mx=max(mx,a[i]);
        }
        for(int i=1;i<=200000;i++)  sum[i]=cnt[i]+sum[i-1];
        ll ans=solve();
        adjust(ans);
        printf("Case #%d: %lld\n",++ks,ans);
    }
    return 0;
}