首页 > 其他 > 详细

解方程【狄利克雷卷积+莫比乌斯反演+积性函数】

时间:2020-10-01 23:55:37      阅读:48      评论:0      收藏:0      [点我收藏+]

题意

数列 \(f(i)\) 使得对任意的 \(n\) 都有:

\[\sum_{i|n}{f(i)\times \sigma_p(\frac{n}{i})}=\sigma_q(n) \]

其中,\(\sigma_k(n)\) 表示 \(n\) 的约数的 \(k\) 次方和。求出 \(f_i\bmod 998244353\ (1\leq i \leq n)\) 的异或和。

\(1\leq n,p,q \leq 10^7,且不保证\ p\leq q\)

题目链接:https://ac.nowcoder.com/acm/contest/7329/F

分析

观察等式的左边,可以发现很符合狄利克雷卷积的形式,即:\((f*\sigma_p)(n)=\sigma_q(n)\)

同时,发现:\(\sigma_k=Id_k*I\),可以得到:\((f*Id_p)(n)=Id_k(n)\),即:

\[\sum_{i|n}{f(i)\times \frac{n^p}{i^p}}=n^q \]

化简得:

\[\sum_{i|n}{\frac{f(i)}{i^p}}=n^{q-p} \]

\(F(n)=n^{q-p},g(n)=\frac{f(n)}{n^p}\),可以发现 \(F(n)\) 得求解很容易,而 \(g(n)\) 得求解较难(这不是刚好满足莫比乌斯反演吗)。根据莫比乌斯反演的约数形式:

\[F(n)=\sum_{d|n}f(d)\Longrightarrow f(n)=\sum_{d|n}{\mu(d)\times F(\frac{n}{d})} \]

可得:

\[g(n)=\frac{f(n)}{n^q}=\sum_{d|n}{\frac{\mu(d)}{d^{q-p}}} \]

显然,\(g(n)\) 是一个积性函数,可以用线性筛处理,关键是如何求出 \(n\) 为质数和 \(i\%\ prime[j]\)\(i*prime[j]\)\(g\) 的函数值。

  • \(n\) 为质数时,代入易得 \(g(n)=1-\frac{1}{n^{q-p}}\)

  • \(i\% prime[j]==0\) 时,有 \(g(i*prime[j])=g(i)\)

  • \(i\%\ prime[j]\neq 0\) 时,根据积性函数,有 \(g(i*prime[j])=g(i)*g(prime[j])\)

对于 \(n^q\) ,由于数据比较大,因此要尽量减少使用快速幂的次数。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e7+7;
const int mod=998244353;
int n,p,q;
bool vis[N];
int prime[N],tol,f[N];
ll num[N];
ll power(ll a,ll b)
{
    ll res=1;
    a%=mod;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int solve()
{
    int ans=0,tol=0;
    f[1]=1;
    num[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++tol]=i;
            if(q<=p) f[i]=(1-power(i,p-q)+mod)%mod;
            else f[i]=(1-power(i,1LL*(q-p)*(mod-2))+mod)%mod;
            num[i]=power(i,q);
        }
        for(int j=1;j<=tol&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            num[i*prime[j]]=num[i]*num[prime[j]]%mod;
            if(i%prime[j]==0)
            {
                f[i*prime[j]]=f[i];
                break;
            }
            else
                f[i*prime[j]]=1LL*f[i]*f[prime[j]]%mod;
        }
    }
    for(int i=1;i<=n;i++)
        ans^=(1LL*f[i]*num[i]%mod);
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&p,&q);
    printf("%d\n",solve());
    return 0;
}

解方程【狄利克雷卷积+莫比乌斯反演+积性函数】

原文:https://www.cnblogs.com/1024-xzx/p/13759097.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!