$f(x)$表示$x$的次大約數，有$f(x)=\frac{x}{x的最小質因數}$，那么

$\begin{array}{rl}\sum _{i=1}^n\sum _{j=1}^{n}sgcd(i,j{)}^k& =\sum _{i=1}^n\sum _{j=1}^{n}f(gcd(i,j){)}^k\\ & =\sum _{d=1}^{n}f(d{)}^k\sum _{i=1}^n\sum _{j=1}^n[gcd(i,j)=d]\\ & =\sum _{d=1}^{n}f(d{)}^k\sum _{i=1}^{?\frac{n}{d}?}\sum _{j=1}^{?\frac{n}{d}?}[gcd(i,j)=1]\\ & =\sum _{d=1}^{n}f(d{)}^k?(2\sum _{i=1}^{?\frac{n}{d}?}\phi (i)?1)\end{array}$
（倒數第二步到最后一步是直接由$?$的定義得到的）

$2\sum _{i=1}^{?\frac{n}{d}?}\phi (i)?1$是經典的杜教篩求歐拉函數前綴和，
然后因為$i$的上界是$?\frac{n}{d}?$所以求出前綴和以后分塊搞一波就好了

$\sum _{d=1}^{n}f(d{)}^k$的求法則非常神仙（%%%網上的大佬）：

$\sum _{d=1}^{n}f(d{)}^k$
$=\sum _{d=2}^{n}f(d{)}^k[d是質數]+\sum _{d=2}^{n}f(d{)}^k[d是合數]+f(1{)}^k$
$=\sum _{d=2}^n[d是質數]+\sum _{d=2}^n(\frac{d}{d的最小質因數}{)}^k[d是合數]$

$\sum _{d=2}^n[d是質數]$即為$n$以內質數個數，可以用min_25篩出來，接下來只需考慮$d$是合數的部分

回憶min_25篩，
設$g(n,j)={\sum }_{i=1}^n{i}^k[i\in Pori的最小質因數>P_j]$，則
當$P_j^2\le n$時，
$g(n,j)=g(n,j?1)?\sum [i的最小質因數=P_j]i^k$
$=g(n,j?1)?P_j^k\sum [i的最小質因數=P_j](\frac{i}{P_j}{)}^k$
$=g(n,j?1)?P_j^k{\sum }_{l=P_j}^{?\frac{n}{P_j}?}[l的最小質因數>P_{j?1}]l^k$
$=g(n,j?1)?P_j^k[g(?\frac{n}{P_j}?,j?1)?g(P_j?1,j?1)]$

我們發現$g(?\frac{n}{P_j}?,j?1)?g(P_j?1,j?1)$
即為${\sum }_{i=1}^n[i的最小質因數=P_j](\frac{i}{P_j}{)}^k$
所以${\sum }_{j=1}^{|P|}g(?\frac{n}{P_j}?,j?1)?g(P_j?1,j?1)$
$={\sum }_{j=1}^{|P|}{\sum }_{i=1}^n[i的最小質因數=P_j](\frac{i}{P_j}{)}^k$
$={\sum }_{i=2}^n(\frac{i}{i的最小質因數}{)}^k$

最后，算$g(n,0)$要快速求${\sum }_{i=1}^n{i}^k$，這里要用第二類斯特林數處理一下：
${\sum }_{i=1}^n{i}^k$
$={\sum }_{i=1}^n{\sum }_{j=1}^k{\{}_j^k\}{i}^{\underline{j}}$
$={\sum }_{j=1}^k{\{}_j^k\}{\sum }_{i=1}^n{i}^{\underline{j}}$
$={\sum }_{j=1}^k{\{}_j^k\}\frac{(n+1{)}^{\underline{j+1}}}{j+1}$

實現細節：
1、取模的話可以自然溢出，$unsignedint$了解一下ovo

2、求下降階乘冪的時候，因為這題的模數不是質數，所以不能快樂求逆元，但是因為$k$比較小所以直接暴力一波，一個一個數乘，這堆數中必定有一個是$j+1$的倍數，所以可以直接先除再乘就好了，注意判斷的時候每次都取模判斷的話會愉快T掉，所以應該在一開始的時候先把余數算出來，然后根據余數的加法定理直接判就好了

參考博客：https://www.cnblogs.com/yoyoball/p/9204846.html

總結

以上是生活随笔為你收集整理的[51NOD1847]奇怪的数学题（杜教筛+min_25筛+第二类斯特林数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。