洛谷P3327 约数个数和结论+莫比乌斯反演

原题

就是让你求\(\sum\limits_{i=1}\sum\limits_{j=1}d(ij)\)（其中\(d(x)\)表示\(x\)的因数个数）

首先有引理（然而并没有证明）：

\(d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)=1]\)

带到原式里得到：

\(ans=\sum\limits_{i=1}\sum\limits_{j=1}\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)=1]\)

利用\(\mu\)函数的性质把方括号换掉：

\(ans=\sum\limits_{i=1}\sum\limits_{j=1}\sum\limits_{x|i}\sum\limits_{y|j}\sum\limits_{d|gcd(x,y)}\mu(d)\)

交换枚举主体：

\(ans=\sum\limits_{x=1}\sum\limits_{y=1}\sum\limits_{i=1}^{\lfloor\frac{N}{x}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{y}\rfloor}\sum\limits_{d|gcd(x,y)}\mu(d)\)

进而得到：

\(ans=\sum\limits_{x=1}\sum\limits_{y=1}\lfloor\frac{N}{x}\rfloor\lfloor\frac{M}{y}\rfloor\sum\limits_{d|gcd(x,y)}\mu(d)\)

首先枚举\(d\)：

\(ans=\sum\limits_{d=1}^{min\{N,M\}}\mu(d)\sum\limits_{x=1}^{\lfloor\frac{N}{d}\rfloor}\sum\limits_{y=1}^{\lfloor\frac{M}{d}\rfloor}\lfloor\frac{N}{x}\rfloor\lfloor\frac{M}{y}\rfloor\)

后面的顺序是无所谓的，交换一下：

\(ans=\sum\limits_{d=1}^{min\{N,M\}}\mu(d)\sum\limits_{x=1}^{\lfloor\frac{N}{d}\rfloor}\lfloor\frac{N}{x}\rfloor\sum\limits_{y=1}^{\lfloor\frac{M}{d}\rfloor}\lfloor\frac{M}{y}\rfloor\)

然后发现只要预处理一下后面的东西就可以整除分块了

贴一下代码：

#include <bits/stdc++.h>

using namespace std;

#define N 50000

int cnt, prime[N+5], mu[N+5], sum[N+5], notprime[N+5];

int b[N+5];

void init()

{

    mu[1] = sum[1] = notprime[1] = 1;

    for(int i = 2; i <= N; ++i)

    {

        if(!notprime[i]) prime[++cnt] = i, mu[i] = -1;

        for(int j = 1; j <= cnt && i*prime[j] <= N; ++j)

        {

            notprime[i*prime[j]] = 1;

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

            {

                mu[i*prime[j]] = 0;

                break;

            }

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

        }

        sum[i] = sum[i-1]+mu[i];

    }

    for(int i = 1; i <= N; ++i)

    {

        for(int l = 1, r; l <= i; l = r+1)

        {

            r = min(i/(i/l), i);

            b[i] += (r-l+1)*(i/l);

        }

    }

}

int T, n, m;

int main()

{

    scanf("%d", &T);

    init();

    while(T--)

    {

        scanf("%d%d", &n, &m);

        long long ans = 0;

        if(n > m) swap(n, m);

        for(int l = 1, r; l <= n; l = r+1)

        {

            r = min(min(n/(n/l), m/(m/l)), n);

            ans += 1LL*(sum[r]-sum[l-1])*b[n/l]*b[m/l];

        }

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

洛谷P3327 约数个数和结论+莫比乌斯反演

最新文章

热门文章

巴特西

洛谷P3327 约数个数和 结论+莫比乌斯反演

最新文章

热门文章

洛谷P3327 约数个数和结论+莫比乌斯反演