[BZOJ2820/Luogu2257]YY的GCD(莫比乌斯反演,数论分块,线性筛)

发布于 2018-01-20  129 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2820/Luogu2257]YY的GCD(莫比乌斯反演,数论分块,线性筛)

Description

神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了,于是向你来请教……多组输入

Http

BZOJ
权限题,提供本站离线版本BZOJch
Luogu

Tag

莫比乌斯反演,数论分块,线性筛

题目大意

求\(\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)\ is\ a\ prime]\)

解决思路

这一题类似,但是有多组数据。
直接从那一题的结尾开始推
\[Ans=\sum_{d=1}^{n} f(d)*\sum_{i=1}^{n/d} \mu(i) \lfloor \frac{n}{id} \rfloor^2\]
另\(T=id\),变枚举\(d\)为枚举\(T\)
\[Ans=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor ^2 \sum_{d|T} [d\ is\ a\ prime]*\mu(\frac{T}{d})\]
后面这个东西\(\sum_{d|T} [d\ is\ a\ prime]*\mu(\frac{T}{d})\)虽然不是积性函数,但是可以线性筛的,具体来说,设\(h(x)=\sum_{d|T} [d\ is\ a\ prime]*\mu(\frac{T}{d})\),那么有
设\(p\)为质数
\(h(p)=1\),这个很容易得到
\(h(p*i)=\mu(i) \quad [gcd(p,i)==p]\)。这个的原理是如果乘进去一个质数\(p\),并且这个\(p\)在\(i\)中已经出现过了,那么在\(\mu(x)\)中就必定有大于等于\(2\)个质因子\(p\),根据莫比乌斯函数的定义\(\mu(x)==0\),所以就只剩\(\mu(i))\)自己的贡献
\(h(p*i)=\mu(i)-h(i) \quad [gcd(p,i)==1]\)。原因是由于乘进去一个互质质数\(p\),原来的莫比乌斯函数要变号,再加上\(mu(i)\)的贡献。
那么结合数论分块,可以做到\(O(n)\)预处理,\(O(\sqrt{n})\)单次询问

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long

const int maxNum=10000010;
const int inf=2147483647;

ll F[maxNum];
int Mu[maxNum];
int pricnt=0,Prime[maxNum/100];
bool notprime[maxNum];

void Init();

int main()
{
    Init();
    int T;scanf("%d",&T);
    while (T--)
    {
        int n,m;scanf("%d%d",&n,&m);if (n>m) swap(n,m);
        ll ans=0;
        for (int i=1,last;i<=n;i=last+1)
        {
            last=min(n/(n/i),m/(m/i));
            ans=ans+(F[last]-F[i-1])*(ll)((n/i))*(ll)((m/i));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

void Init()
{
    Mu[1]=1;F[1]=0;notprime[1]=1;
    for (int i=2;i<maxNum;i++)
    {
        if (notprime[i]==0) Prime[++pricnt]=i,Mu[i]=-1,F[i]=1;
        for (int j=1;(j<=pricnt)&&((ll)i*(ll)Prime[j]<maxNum);j++)
        {
            notprime[i*Prime[j]]=1;
            if (i%Prime[j]==0)
            {
                F[i*Prime[j]]=Mu[i];
                break;
            }
            Mu[i*Prime[j]]=-Mu[i];
            F[i*Prime[j]]=Mu[i]-F[i];
        }
    }
    for (int i=1;i<maxNum;i++) F[i]+=F[i-1];
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2820/Luogu2257]YY的GCD(莫比乌斯反演,数论分块,线性筛)


HNCJ OIer