没有什么理由不拼尽全力了
3.6
今天做了 JZPKIL , 复习了一下反演/积性函数相关的一点知识/伯努利数/Pollard's rho 的写法
下午看了看 AHC 的题和鱼鱼出的比赛题都感觉不太会，我好弱啊/kk
(sum gcd^x(i,n)lcm^y(i,n) = n^ysum gcd^{x-y}(i,n)i^y)
忽略 (n^y) 并枚举因数 :
(large = sumlimits_{d|n} d^x sumlimits_{ileq frac{n}{d}} i^y [(i,frac{n}{d})=1])
(large = sumlimits_{d|n}d^x sumlimits_{p|frac{n}{d}} mu(p)p^y sumlimits_{i=1}^{frac{n}{dp}}i^y)
由于自然数 (k) 次幂和是一个 (k+1) 次多项式 (sum a_ix^i) , 因此我们可以分开考虑每一项对答案的贡献.
考虑一个 (a_ix^i) 对答案的贡献.
此时令 (F(n)=n^x,G(n)=mu(n)n^y,H(n)=n^i),我们要算的就是 (F/G/H) 三个积性函数的狄利克雷卷积的第 (n) 项的值.
乘以 (a_i) 就可以算出 (a_ix^i) 这一项对答案的贡献。
由于 (F/G/H) 都是积性函数所以答案函数是关于 (n) 的积性函数， (pollard-rho) 分解质因子然后计算即可。
接下来问题是如何算出这个多项式的系数。
(Theta(n^2)) 插值是不行的因为有 (100) 组数据
那就只能用伯努利数了。
伯努利数
(large B_0=1)
(large sumlimits_{i=0}^n B_i inom{n+1}{i} = 0 quad (n>0))
(large S(n,k) = sumlimits_{i=0}^{n-1} i^k = frac{1}{k+1} sumlimits_{i=0}^k inom{k+1}{i}B_in^{k+1-i})
可以 (Theta(n^2)) 求出 (B_0...B_n) , 当然也可以用 (B(x) = large frac{x}{e^x-1}) (Theta(n log n)) 算。
复杂度不想分析，反正能跑
3.7
开了个新坑 SAM-review , 写 SAM 板子.