「Luogu2257」YY的GCD

骑猪看日落 2022-01-08 02:35 167阅读 0赞

# 「Luogu2257」YY的GCD #

蒟蒻的第一道莫反

跟着题解推的式子，但还是记录一下过程吧

本文可能在一定程度上存在谬误，请谨慎分析

若发现文中有错误，如您愿意，恳请您向我指出，不胜感激

--------------------

[problem][]

# Solution #

题目要求：

\\\[ans=\\sum\_\{i=1\}^N\\sum\_\{j=1\}^M\[gcd(i,j)\\in prime\]\\\]

令\\(f(p)=\\sum\_\{i=1\}^N\\sum\_\{j=1\}^M\[gcd(i,j)=p\](p\\in prime)\\)

再令\\(g(p)=\\sum\_\{i=1\}^N\\sum\_\{j=1\}^M\[p|gcd(i,j)\](p\\in prime)\\)

于是有

\\\[g(n)=\\sum\_\{n|d\}f(d)\\\]

反演后可得

\\\[f(n)=\\sum\_\{n|d\}\\mu(\\frac\{d\}\{n\})g(d)\\\]

又知\\(g(d)=\\lfloor\\frac\{N\}\{d\}\\rfloor\\lfloor\\frac\{M\}\{d\}\\rfloor\\)

于是有

\\\[ans=\\sum\_\{n\\in prime\}f(n)=\\sum\_\{n\\in prime\}\\sum\_\{n|d\}\\mu (\\frac\{d\}\{n\})\\lfloor\\frac\{N\}\{d\}\\rfloor\\lfloor\\frac\{M\}\{d\}\\rfloor\\\\=\\sum\_\{n|d\}\\lfloor\\frac\{N\}\{d\}\\rfloor\\lfloor\\frac\{M\}\{d\}\\rfloor\\sum\_\{n\\in prime\}\\mu(\\frac\{d\}\{n\})\\\\=\\sum\_\{d=1\}^\{min(N,M)\}\\lfloor\\frac\{N\}\{d\}\\rfloor\\lfloor\\frac\{M\}\{d\}\\rfloor\\sum\_\{n|d,n\\in prime\}\\mu(\\frac\{d\}\{n\})\\\]

令\\(sum(d)=\\sum\_\{n|d,n\\in prime\}\\mu(\\frac\{d\}\{n\})\\)，预处理\\(sum(d)\\)

那么答案即

\\\[ans=\\sum\_\{d=1\}^\{min(M,N)\}\\lfloor\\frac\{N\}\{d\}\\rfloor\\lfloor\\frac\{M\}\{d\}\\rfloor sum(d)\\\]

\\(\\sum sum(d)\\)仍可以利用前缀和优化，\\(\\sum\\lfloor\\frac\{N\}\{d\}\\rfloor\\lfloor\\frac\{M\}\{d\}\\rfloor\\)利用整除分块优化，最终时间复杂度为\\(O(T\\sqrt\{min(N,M)\}+k)\\)，\\(k\\)为预处理复杂度

# Code #

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #define maxn 10000005
    #define N 10000000
    using namespace std;
    typedef long long ll;
    
    template <typename T> void read(T &t)
    {
        t=0;int f=0;char c=getchar();
        while(!isdigit(c)){f|=c=='-';c=getchar();}
        while(isdigit(c)){t=t*10+c-'0';c=getchar();}
        if(f)t=-t;
    }
    
    int T;
    int n,m;
    int pri[maxn],pcnt,nop[maxn];
    int mu[maxn];
    ll sum[maxn],up;
    
    void GetPrime()
    {
        nop[1]=1,mu[1]=1;
        for(register int i=2;i<=N;++i)
        {
            if(!nop[i])pri[++pcnt]=i,mu[i]=-1; 
            for(register int j=1;j<=pcnt && i*pri[j]<=N;++j)
            {
                nop[i*pri[j]]=1;
                if(i%pri[j]==0)break;
                else mu[i*pri[j]]=-mu[i];
            }
        }
        for(register int i=1;i<=pcnt;++i)
            for(register int j=1;pri[i]*j<=N;++j)
                sum[pri[i]*j]+=mu[j];
        for(register int i=1;i<=N;++i)
            sum[i]+=sum[i-1];
    }
    
    ll Calc()
    {
        ll re=0;
        for(register int l=1,r;l<=up;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            re+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
        }
        return re;
    }
    
    int main()
    {
        read(T);
        GetPrime();
        while(T--)
        {
            read(n),read(m);
            up=min(n,m);
            printf("%lld\n",Calc());
        }
        return 0;
    }

转载于:https://www.cnblogs.com/lizbaka/p/10508947.html

[problem]: https://www.luogu.org/problemnew/show/P2257