[湖北省队互测2014]一个人的数论
给定 (n,d)，计算 (f_d(n))
其中 (f_d(n)) 为 ([1,n]) 中所有与 (n) 互质的数的 (d) 次幂之和。
由于 (n) 非常大，所以给出其因式分解式，(p_1^{a_1}p_2^{a_2}...)，保证分解后的项数至多为 (10^3)，(p,ale 10^9) 且 (p) 均为质数。
(dle 100,wle 10^3)
( m Sol:)
答案是：
[egin{aligned}
&sum_{i=1}^n [gcd(i,n)=1] imes i^d
\&=sum_{i=1}^n sum_{t|n,t|i} mu(t) imes i^d
\&=sum_{t|n} mu(t)t^d imes S(frac{n}{t})
end{aligned}]
对于自然数幂和，通过伯努利多项式展开：
[egin{aligned}
&sum_{t|n} mu(t)t^d imes S(frac{n}{t})
\&=sum_{t|n}mu(t)t^d imes sum_{j=0}^{d+1} f_j imes (frac{n}{t})^j
\&=sum_{j=0}^{d+1} f_j imes n^j sum_{t|n} mu(t) imes t^{d-j}
end{aligned}]
注意到 (n) 的给出为因式分解形式，(mu(t) e 0) 当且仅当每个质数出现且仅出现一次。
枚举 (j)，统计答案只需要统计 (t^{d-j})，每个元素相当于一个多项式 ((1-t^{d-j}))，直接算即可？
复杂度是 (mathcal O(d imes w+d^2))，直接伯努利数他不香吗。。。