除了最后一题都比较简单就写一起了

P4450-双亲数

题目链接:https://www.luogu.com.cn/problem/P4450

题目大意

给出\(A,B,d\)求有多少对\((a,b)\)满足\(gcd(a,b)=d\)且\(a\in[1,A],b\in[1,B]\)

解题思路

很显然的容斥，枚举\(d\)的倍数\(i\)，然后容斥系数就是\(\mu(\frac{i}{d})\)。

时间复杂度\(O(n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6+10;

int A,B,d,mu[N],pri[N],cnt;

long long ans;

bool v[N];

int main()

{

    scanf("%d%d%d",&A,&B,&d);

    mu[1]=1;

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

        if(!v[i])pri[++cnt]=i,mu[i]=-1;

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

            v[i*pri[j]]=1;

            if(i%pri[j]==0)break;

            mu[i*pri[j]]=-mu[i];

        }

    }

    if(A>B)swap(A,B);

    for(int i=d;i<=A;i+=d)

        ans+=1ll*(A/i)*(B/i)*mu[i/d];

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

}

P5221-Product

题目链接:https://www.luogu.com.cn/problem/P5221

题目大意

给出\(n\)求

\[\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{gcd(i,j)}
\]

解题思路

\(\text{CYJian}\)的题啊，时限\(0.2s?\)不过只是看起来花里胡哨，没有其他\(\text{CYJian}\)的题那么难。

先简单把\(lcm\)拆出来化一下式子

\[\left(\prod_{i=1}^n\prod_{j=1}^ni\times j\right)\frac{1}{\left(\prod_{i=1}^{n}\prod_{j=1}^ngcd(i,j)\right)^2}
\]

左边那个很容易求就是\((n!)^{2n}\)，右边那个因为是乘积所以很好做，直接枚举质数幂\(d^e\)，让有\(\lfloor\frac{n}{d^e}\rfloor^2\)对数的\(gcd\)包含\(d^e\)，会产生这么多的贡献，但是因为在\(d^{e-1}\)的时候也统计过一次，所以只需要产生\(d\)的贡献就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1e6+10,P=104857601;

ll n,ans,cnt,pri[N];

bool v[N];

ll power(ll x,ll b){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%P;

        x=x*x%P;b>>=1;

    }

    return ans;

}

signed main()

{

    scanf("%lld",&n);ans=1;

    for(ll i=2;i<=n;i++){

        if(!v[i]){

            for(ll j=i;j<=n;j=j*i)

                ans=ans*power(i,(n/j)*(n/j)%(P-1))%P;

            pri[++cnt]=i;

        }

        for(ll j=1;j<=cnt&&i*pri[j]<=n;j++){

            v[i*pri[j]]=1;

            if(i%pri[j]==0)break;

        }

    }

    ans=power(ans*ans%P,P-2);

    ll f=1;

    for(ll i=1;i<=n;i++)f=f*i%P;

    f=power(f,2*n);ans=ans*f%P;

    printf("%lld",ans);

    return 0;

}

P6055-[RC-02]GCD

题目链接:https://www.luogu.com.cn/problem/P6055

题目大意

给出\(n\)求

\[\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor\frac{n}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{n}{j}\rfloor}[gcd(i,j)=1][gcd(p,q)=1]
\]

解题思路

刚开始还以为可以直接暴力整除分块+杜教筛欧拉函数然后\(O(n^{\frac{3}{4}})\)搞，然后发现时限是\(1s\)。

发现这个式子的顺序很奇怪，特意的把\(j\)放在了里面。这个提示我们\(j\)其实是在枚举\(p\)和\(q\)的\(gcd\)。

而又\(j\)和\(i\)互质，其实这个式子的真正目的是对于每个\(i\)求有多少对数的\(gcd\)和\(i\)互质然后求和。换成式子就是

\[\sum_{i=1}^n\sum_{q=1}^n\sum_{p=1}^n[gcd(gcd(q,p),i)=1]
\]

就是三对数之间互质的对数，之间上莫反就可以了

\[\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor^3\mu(i)
\]

\(n\)比较大，要用杜教筛筛一下\(mu\)

时间复杂度\(O(n^{\frac{2}{3}})\)？

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const ll N=1e7+10,P=998244353;

ll n,cnt,pri[N],mu[N],ans;

map<ll,ll> mp;

bool v[N];

ll get_sum(ll n){

    if(mp.find(n)!=mp.end())return mp[n];

    if(n<N)return mu[n];

    ll rest=1;

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

        r=n/(n/l),(rest+=P-(r-l+1)*get_sum(n/l))%=P;

    return mp[n]=rest;

}

signed main()

{

    scanf("%lld",&n);mu[1]=1;

    for(ll i=2;i<N;i++){

        if(!v[i])pri[++cnt]=i,mu[i]=-1;

        for(ll j=1;j<=cnt&&i*pri[j]<N;j++){

            v[i*pri[j]]=1;

            if(i%pri[j]==0)break;

            mu[i*pri[j]]=-mu[i];

        }

    }

    for(ll i=1;i<N;i++)(mu[i]+=mu[i-1])%=P;

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

        r=n/(n/l);

        ll p=n/l;p=p*p%P*p%P;

        (ans+=p*(get_sum(r)-get_sum(l-1))%P)%=P;

    }

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

    return 0;

}

巴特西

P4450-双亲数,P5221-Product,P6055-[RC-02]GCD【莫比乌斯反演,杜教筛】

P4450-双亲数

题目大意

解题思路

code

P5221-Product

题目大意

解题思路

code

P6055-[RC-02]GCD

题目大意

解题思路

code

最新文章

热门文章