结论：

证明：

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

交换求和符号：

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

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

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

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

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

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