这道反演题, 真牛逼.
以下用 $B$ 代表伯努利数,$l*g=f$ 代表狄利克雷卷积, 先推式子.
对于给出的 $n,x,y$ 求一百组数据的 $ans$
- $\begin{
- array
- }{
- rcl
- } ans & = & \sum\limits_{
- i=1
- }^ngcd(i,n)^xlcm(i,n)^y\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & \sum\limits_{
- i=1
- }^ngcd(i,n)^x\frac{
- (in)^y
- }{
- gcd(i,n)^y
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & \sum\limits_{
- i=1
- }^ngcd(i,n)^{
- x-y
- }(in)^y\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & n^y\sum\limits_{
- i=1
- }^ni^ygcd(i,n)^{
- x-y
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & n^y\sum\limits_{
- d|n
- }d^{
- x-y
- } \sum \limits_{
- i=1
- }^{
- \lfloor \frac{
- n
- }{
- d
- } \rfloor
- } (id)^y[gcd(i,\lfloor\frac{
- n
- }{
- d
- } \rfloor)=1]\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & n^y\sum\limits_{
- d|n
- }d^x\sum\limits_{
- i=1
- }^{
- \lfloor \frac{
- n
- }{
- d
- } \rfloor
- }i^y\sum\limits_{
- t|gcd(i,\lfloor \frac{
- n
- }{
- d
- } \rfloor)
- }\mu(t)\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & n^y\sum\limits_{
- d|n
- }d^x\sum\limits_{
- t|\lfloor\frac{
- n
- }{
- d
- }\rfloor
- }\mu(t)t^y\sum\limits_{
- i=1
- }^{
- \lfloor\frac{
- n
- }{
- td
- }\rfloor
- }i^y\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- }\sum\limits_{
- i=0
- }^{
- \lfloor\frac{
- n
- }{
- td
- }\rfloor
- }i^y & = & \frac{
- 1
- }{
- y+1
- }\sum\limits_{
- i=0
- }^yC_{
- y+1
- }^iB_i(\lfloor\frac{
- n
- }{
- td
- }\rfloor)^{
- y-i+1
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- }R_i & = & \frac{
- C_{
- y+1
- }^iB_i
- }{
- y+1
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- }ans & = & n^y\sum\limits_{
- d|n
- }d^x\sum\limits_{
- t|\lfloor\frac{
- n
- }{
- d
- }\rfloor
- }\mu(t)t^y\sum\limits_{
- i=0
- }^yR_i(\lfloor\frac{
- n
- }{
- td
- }\rfloor)^{
- y-i+1
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & \sum\limits_{
- i=1
- }^yR_in^y\sum\limits_{
- d|n
- }d^x\sum\limits_{
- t|\lfloor\frac{
- n
- }{
- d
- }\rfloor
- }\mu(t)t^y(\lfloor\frac{
- n
- }{
- td
- }\rfloor)^{
- y-i+1
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- }f_{
- i,x,y
- }(n) & = & n^y\sum\limits_{
- d|n
- }d^x\sum\limits_{
- t|\lfloor\frac{
- n
- }{
- d
- }\rfloor
- }\mu(t)t^y(\lfloor\frac{
- n
- }{
- td
- }\rfloor)^{
- y-i+1
- }\end{
- array
- }$
分析 $f_{i,x,y}(n)$.
- $\begin{
- array
- }{
- rcl
- }l(x) & = & \mu(x)x^y \end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } q_r(x)=x^r\end{
- array
- }$
$l,q$ 均为积性函数.
- $\begin{
- array
- }{
- rcl
- }g(n) & = & \sum\limits_{
- d|n
- }\mu(d)d^yq(\lfloor\frac{
- n
- }{
- d
- }\rfloor)\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- }g(n) & = & l(n)*q(n)\end{
- array
- }$
也为积性函数.
$\begin{array}{rcl}f(n) & = & \sum\limits_{d|n}q(d)g(\lfloor\frac{n}{d}\rfloor)\\ & = & q(n)*g(n)\end{array}$
所以 $f_{i,x,y}(n)$ 是积性函数.
$\begin{array}{rcl}ans & = & \sum\limits_{i=0}^yR_if_{i,x,y}(n)\end{array}$
$n$ 为 $1e18$ 考虑用 $O(n{1/4})$ 的 $Pollard_Rho$ 算法对 $n$ 进行质因分解.
- $n=\_p^c$
- $\begin{
- array
- }{
- rcl
- }f_{
- i,x,y
- }(p^c) & = & p^{
- cy
- }\sum\limits_{
- d|p^c
- }\sum\limits_{
- t|\lfloor\frac{
- p^c
- }{
- d
- }\rfloor
- }\mu(t)t^y(\lfloor\frac{
- p^c
- }{
- td
- }\rfloor)^{
- y-i+1
- }\end{
- array
- }$
- $\begin{
- array
- }{
- rcl
- } & = & p^{
- cy
- }\sum\limits_{
- j=0
- }^cp^{
- jx
- }\sum\limits_{
- k=0
- }^{
- c-j
- }\mu(p^k)p^{
- ky
- }(p^{
- c-j-k
- })^{
- y-i+1
- }\end{
- array
- }$
当 k=1 或者 0 的时候, 莫比乌斯函数不为 0.
$\begin{array}{rcl} & = & p^{cy}\sum\limits_{j=0}^c p^{jx}[(p^{c-j})^{y-i+1}-p^y(p^{c-j-1})^{y-i+1}]\end{array}$
问题得到解决.
知识点:
莫比乌斯反演
狄利克雷卷积
积性函数
自然数幂和
伯努利数
$Miller\_Rabin$ 素数测试
$Pollard\_Rho$ 质因数分解
费马小定理
二次初探原理
生日悖论
有兴趣的可以尝试一下, 是道好题.
来源: http://www.bubuko.com/infodetail-3159819.html