BZOJ 2820/2818 : YY的GCD – [莫比乌斯反演]

题目传送门

题解

不多说,上式子
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}isprime[gcd(i, j)]

下文isprime简写成is

默认n<m,如果不是请swap(n, m)

枚举gcd为d

\sum\limits_{d=1}^{n}is[d]\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i, j)\;=\;\;\;d]

除d

\sum\limits_{d=1}^{n}is[d]\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i, j)\; = \;\;\; 1]

反演

\sum\limits_{d=1}^{n}is[d]\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p\mid gcd(i, j)}\mu(p)

把p放前面枚举

\sum\limits_{d=1}^{n}is[d]\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor

令Q = dp,枚举Q

\sum\limits_{Q=1}^{n}\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor\sum\limits_{d\mid Q}is[d]\;\;\times\;\;\mu(\frac{Q}{d})

f(x) = \sum\limits_{d\mid Q}is[d]\;\;\times\;\;\mu(\frac{x}{d})

上面的f可以线性筛也可以n\times \;\;\ln n暴力得出,然后分段求和就好

附代码 上面暴力,下面线筛f

#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 10001000;
bool vis[N];
int pr[N>>1], f[N], mu[N], tot, sum[N];
void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i ++ ) {
        if(!vis[i]) {pr[++tot] = i, mu[i] = -1;}
        for(int j = 1; j <= tot && pr[j]i < N; j ++ ) {
            vis[ipr[j]] = 1;
            if(i%pr[j]  0) break;
            mu[ipr[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= tot; i ++ ) for(int j = 1; pr[i]j < N; j ++ ) 
        f[pr[i]j]+=mu[j];
    for(int i = 1; i < N; i ++ ) sum[i] = sum[i-1] + f[i];
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        if(n > m) swap(n, m);
        int lst;
        ll ans = 0;
        for(int i = 1; i <= n; i = lst+1) {
            lst = min(n/(n/i), m/(m/i));
            ans += ((ll)sum[lst]-sum[i-1])(n/i)*(m/i);
        }
        printf("%lld\n", ans);
    }
}

#include 
#include 
#include 
#include 
using namespace std;
const int N = 11000000;
bool np[N+10];
int mu[N+10], tot, pr[N+10], sum[N+10];
int f[N+10];
int t, n, m;
void init() {
    mu[1]=1;
    for(int i=2;i<=N;i++) {
        if(!np[i]) {
            pr[++tot]=i;
            mu[i]=-1;
            f[i]=1;
        }
        for(int j=1;j<=tot&&i*pr[j]<=N;j++) {
            np[i*pr[j]]=1;
            if(!(i%pr[j])) {
                mu[i*pr[j]]=0;
                f[i*pr[j]]=mu[i];
                break;
            }
            mu[i*pr[j]]=-mu[i];
            f[i*pr[j]]=mu[i]-f[i];
        }
        sum[i]=sum[i-1]+f[i];
    }
}
void solve(int n, int m) {
    if(n>m)swap(n,m);
    int lst;
    long long ans=0;
    for(int i=1;i<=n;i=lst+1) {
        lst = min(n/(n/i), m/(m/i));
        ans+=1ll*(sum[lst]-sum[i-1])*(n/i)*(m/i);
    }
    printf("%lld\n", ans);
}
int main() {
    init();
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        solve(n,m);
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注