【题解】Luogu P2522 [HAOI2011]Problem b

原题传送门

这题需要运用莫比乌斯反演(懵逼钨丝繁衍)

我们看题面，让求对于区间$[a,b]$内的整数x和$[c,d]$内的y，满足$ gcd(x,y)=k$的数对的个数

我们珂以跟容斥原理（二维前缀和）一样来求答案：

设$solve(x,y,k)$表示对于区间$[1,x]$内的整数x和$[1,y]$内的y，满足$gcd(x,y)=k$的数对的个数

那么答案$ans=solve(b,d,k)-solve(a-1,d,k)-solve(b,c-1,k)+solve(a-1,c-1,k)$

那么solve怎么写呢？

设F(n)表示满足$gcd(x,y)\%t=0$的数对个数，f(t)表示满足$gcd(x,y)=t$的数对个数，实际上答案就是f(k)

这就满足莫比乌斯反演的关系式了

显然我们珂以得知$F(t)=(b/t)*(d/t)$

我们根据反演的第二个公式便珂以得出

$$f(k)=\sum_{n|k}\mu(\frac{k}{n})F(k)$$

再加上整除分块就珂以了

#include <bits/stdc++.h>

#define N 50005

#define ll long long

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register ll x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Min(register int a,register int b)

{

    return a<b?a:b;

}

int miu[N],v[N],sum[N];

inline ll solve(register int a,register int b,register int k)

{

    int maxround=Min(a/k,b/k);

    ll ans=0;

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

    {

        r=Min((a/k)/((a/k)/l),(b/k)/((b/k)/l));

        ans+=(ll)((a/k)/l)*((b/k)/l)*(sum[r]-sum[l-1]);

    }

    return ans;

}

int main()

{

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

        miu[i]=1,v[i]=0;

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

    {

        if(v[i])

            continue;

        miu[i]=-1;

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

        {

            v[j]=1;

            if((j/i)%i==0)

                miu[j]=0;

            else

                miu[j]*=-1;

        }

    }

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

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

    int t=read();

    while(t--)

    {

        int a=read()-1,b=read(),c=read()-1,d=read(),k=read();

        ll ans=solve(b,d,k)-solve(a,d,k)-solve(b,c,k)+solve(a,c,k);

        write(ans),puts("");

    }

    return 0;

 }

巴特西

【题解】Luogu P2522 [HAOI2011]Problem b

原题传送门

这题需要运用莫比乌斯反演(懵逼钨丝繁衍)

我们看题面，让求对于区间\([a,b]\)内的整数x和\([c,d]\)内的y，满足$ gcd(x,y)=k$的数对的个数

我们珂以跟容斥原理（二维前缀和）一样来求答案：

设\(solve(x,y,k)\)表示对于区间\([1,x]\)内的整数x和\([1,y]\)内的y，满足\(gcd(x,y)=k\)的数对的个数

那么答案\(ans=solve(b,d,k)-solve(a-1,d,k)-solve(b,c-1,k)+solve(a-1,c-1,k)\)

那么solve怎么写呢？

设F(n)表示满足\(gcd(x,y)\%t=0\)的数对个数，f(t)表示满足\(gcd(x,y)=t\)的数对个数，实际上答案就是f(k)

这就满足莫比乌斯反演的关系式了

显然我们珂以得知\(F(t)=(b/t)*(d/t)\)

我们根据反演的第二个公式便珂以得出

$$f(k)=\sum_{n|k}\mu(\frac{k}{n})F(k)$$

再加上整除分块就珂以了

最新文章

热门文章