1 条题解

  • 1
    @ 2024-8-19 14:59:42

    结论:

    $$ \sum^n_{i=1}\sum_{j=1}^{\lfloor \frac n i \rfloor }\sum_{k|i} {j^mk^m\mu(k)}=n $$

    证明:

    我们只需要对其小小地变形:

    $$\sum^n_{i=1}\sum_{j=1}^{\lfloor \frac n i \rfloor }\sum_{k|i} {j^mk^m\mu(k)}\\ =\sum^n_{i=1}\sum_{k|i} ({k^m\mu(k)\sum_{j=1}^{\lfloor \frac n i \rfloor }j^m}) $$

    交换求和符号:

    $$=\sum^n_{k=1}\sum_{k|i} ({k^m\mu(k)\sum_{j=1}^{\lfloor \frac n i \rfloor }j^m})\\ =\sum^n_{k=1}(k^m\mu(k)\sum_{k|i} {\sum_{j=1}^{\lfloor \frac n i \rfloor }j^m}) $$

    我们画一个图:横轴表示ii,纵轴表示jj,令(i,j)这个点的贡献为jmj^m,那么最里面的求和符号,就是计算第i列的所有点的贡献之和。

    如图

    这是从i的视角,我们不妨从j的视角这样看,我们发现,第j行最右侧的点横坐标是nj\lfloor \frac n j \rfloor,它的每kk个距离有1份贡献,那么总共有$\lfloor \frac{\lfloor \frac n j \rfloor } k \rfloor=\lfloor \frac n {jk} \rfloor$个贡献。 所以

    $$\sum^n_{k=1}(k^m\mu(k)\sum_{k|i} {\sum_{j=1}^{\lfloor \frac n i \rfloor }j^m})\\ =\sum_{1\le j,k\le n}(j^mk^m{\lfloor \frac n {jk} \rfloor}\mu(k))\\ $$

    x=jk,x>nx=jk,x>n时右边显然为0,所以只需要对1xn1\le x\le n求和,k为x的因数。

    $$=\sum_{1\le x\le n,k|x}x^m{\lfloor \frac n {x} \rfloor}\mu(k)\\ =\sum_{1\le x\le n}(x^m{\lfloor \frac n {x} \rfloor}\sum_{k|x}\mu(k))\\ $$

    根据莫比乌斯函数的性质:

    kxμ(k)=[x=1]\sum_{k|x}\mu(k)=[x=1]\\

    意思是只有x=1时,值是1,其他时候都是0. 代入得:

    $$=\sum_{1\le x\le n}(x^m{\lfloor \frac n {x} \rfloor}[x=1])\\ =n $$

    所以这个式子答案是n. 输出n mod pn\ mod\ p即可:

    • 1

    信息

    ID
    1612
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    4
    已通过
    1
    上传者