迪狄利克雷函数简单表达式有反函数吗？

来源：蜘蛛抓取(WebSpider) 时间：2024-01-07 12:30 标签： 狄利克雷函数简单表达式
数列 \(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;
}

我要回帖

更多关于 狄利克雷函数简单表达式 的文章

 

随机推荐