网站技术介绍,可以做语文阅读题的网站,马鞍山建站,上海网站建设 知名做f(x)f(x)f(x)表示xxx的次大约数#xff0c;有f(x)xx的最小质因数f(x)\frac{x}{x的最小质因数}f(x)x的最小质因数x#xff0c;那么 ∑i1n∑j1nsgcd(i,j)k∑i1n∑j1nf(gcd(i,j))k∑d1nf(d)k∑i1n∑j1n[gcd(i,j)d]∑d1nf(d)k∑i1⌊nd⌋∑j1⌊nd⌋[gcd(i,j)1]∑d1nf(d)k⋅(2∑i…f(x)f(x)f(x)表示xxx的次大约数有f(x)xx的最小质因数f(x)\frac{x}{x的最小质因数}f(x)x的最小质因数x那么
∑i1n∑j1nsgcd(i,j)k∑i1n∑j1nf(gcd(i,j))k∑d1nf(d)k∑i1n∑j1n[gcd(i,j)d]∑d1nf(d)k∑i1⌊nd⌋∑j1⌊nd⌋[gcd(i,j)1]∑d1nf(d)k⋅(2∑i1⌊nd⌋φ(i)−1)\begin{aligned} \sum\limits_{i1}^{n}\sum\limits_{j1}^{n}sgcd(i,j)^k\sum\limits_{i1}^n\sum\limits_{j1}^{n}f(gcd(i,j))^k\\ \sum\limits_{d1}^{n}f(d)^k\sum\limits_{i1}^{n}\sum\limits_{j1}^{n}[gcd(i,j)d]\\ \sum\limits_{d1}^{n}f(d)^k\sum\limits_{i1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j1}^{\lfloor \frac{n}{d}\rfloor}[gcd(i,j)1]\\ \sum\limits_{d1}^{n}f(d)^k\cdot(2\sum\limits_{i1}^{\lfloor \frac{n}{d}\rfloor}\varphi(i)-1) \end{aligned}i1∑nj1∑nsgcd(i,j)ki1∑nj1∑nf(gcd(i,j))kd1∑nf(d)ki1∑nj1∑n[gcd(i,j)d]d1∑nf(d)ki1∑⌊dn⌋j1∑⌊dn⌋[gcd(i,j)1]d1∑nf(d)k⋅(2i1∑⌊dn⌋φ(i)−1) 倒数第二步到最后一步是直接由ϕϕϕ的定义得到的
2∑i1⌊nd⌋φ(i)−12\sum\limits_{i1}^{\lfloor \frac{n}{d}\rfloor}\varphi(i)-12i1∑⌊dn⌋φ(i)−1是经典的杜教筛求欧拉函数前缀和 然后因为iii的上界是⌊nd⌋\lfloor\frac{n}{d}\rfloor⌊dn⌋所以求出前缀和以后分块搞一波就好了
∑d1nf(d)k\sum\limits_{d1}^{n}f(d)^kd1∑nf(d)k的求法则非常神仙%%%网上的大佬
∑d1nf(d)k\sum\limits_{d1}^{n}f(d)^kd1∑nf(d)k ∑d2nf(d)k[d是质数]∑d2nf(d)k[d是合数]f(1)k\sum\limits_{d2}^{n}f(d)^k[d是质数]\sum\limits_{d2}^{n}f(d)^k[d是合数]f(1)^kd2∑nf(d)k[d是质数]d2∑nf(d)k[d是合数]f(1)k ∑d2n[d是质数]∑d2n(dd的最小质因数)k[d是合数]\sum\limits_{d2}^{n}[d是质数]\sum\limits_{d2}^{n}(\frac{d}{d的最小质因数})^k[d是合数]d2∑n[d是质数]d2∑n(d的最小质因数d)k[d是合数]
∑d2n[d是质数]\sum\limits_{d2}^{n}[d是质数]d2∑n[d是质数]即为nnn以内质数个数可以用min_25筛出来接下来只需考虑ddd是合数的部分
回忆min_25筛 设g(n,j)∑i1nik[i∈Pori的最小质因数Pj]g(n,j)\sum_{i1}^ni^k[i\in P\ \ or \ \ i的最小质因数P_j ]g(n,j)∑i1nik[i∈P or i的最小质因数Pj]则 当Pj2≤nP_j^2\leq nPj2≤n时 g(n,j)g(n,j−1)−∑[i的最小质因数Pj]ikg(n,j)g(n,j-1)-\sum[i的最小质因数P_j]i^kg(n,j)g(n,j−1)−∑[i的最小质因数Pj]ik g(n,j−1)−Pjk∑[i的最小质因数Pj](iPj)kg(n,j-1)-P_j^k\sum[i的最小质因数P_j](\frac{i}{P_j})^kg(n,j−1)−Pjk∑[i的最小质因数Pj](Pji)k g(n,j−1)−Pjk∑lPj⌊nPj⌋[l的最小质因数Pj−1]lkg(n,j-1)-P_j^k\sum_{lP_j}^{\lfloor\frac{n}{P_j}\rfloor}[l的最小质因数P_{j-1}]l^kg(n,j−1)−Pjk∑lPj⌊Pjn⌋[l的最小质因数Pj−1]lk g(n,j−1)−Pjk[g(⌊nPj⌋,j−1)−g(Pj−1,j−1)]g(n,j-1)-P_j^k[g(\lfloor\frac{n}{P_j}\rfloor,j-1)-g(P_j-1,j-1)]g(n,j−1)−Pjk[g(⌊Pjn⌋,j−1)−g(Pj−1,j−1)]
我们发现g(⌊nPj⌋,j−1)−g(Pj−1,j−1)g(\lfloor\frac{n}{P_j}\rfloor,j-1)-g(P_j-1,j-1)g(⌊Pjn⌋,j−1)−g(Pj−1,j−1) 即为∑i1n[i的最小质因数Pj](iPj)k\sum_{i1}^{n}[i的最小质因数P_j](\frac{i}{P_j})^k∑i1n[i的最小质因数Pj](Pji)k 所以∑j1∣P∣g(⌊nPj⌋,j−1)−g(Pj−1,j−1)\sum_{j1}^{|P|}g(\lfloor\frac{n}{P_j}\rfloor,j-1)-g(P_j-1,j-1)∑j1∣P∣g(⌊Pjn⌋,j−1)−g(Pj−1,j−1) ∑j1∣P∣∑i1n[i的最小质因数Pj](iPj)k\sum_{j1}^{|P|}\sum_{i1}^{n}[i的最小质因数P_j](\frac{i}{P_j})^k∑j1∣P∣∑i1n[i的最小质因数Pj](Pji)k ∑i2n(ii的最小质因数)k\sum_{i2}^{n}(\frac{i}{i的最小质因数})^k∑i2n(i的最小质因数i)k
最后算g(n,0)g(n,0)g(n,0)要快速求∑i1nik\sum_{i1}^{n}i^k∑i1nik这里要用第二类斯特林数处理一下 ∑i1nik\sum_{i1}^{n}i^k∑i1nik ∑i1n∑j1k{jk}ij‾\sum_{i1}^{n}\sum_{j1}^{k}\{_j^k\}i^{\underline{j}}∑i1n∑j1k{jk}ij ∑j1k{jk}∑i1nij‾\sum_{j1}^{k}\{_j^k\}\sum_{i1}^{n}i^{\underline j}∑j1k{jk}∑i1nij ∑j1k{jk}(n1)j1‾j1\sum_{j1}^{k}\{_j^k\}\frac{(n1)^{\underline{j1}}}{j1}∑j1k{jk}j1(n1)j1
实现细节 1、取模的话可以自然溢出unsignedintunsigned\ intunsigned int了解一下ovo
2、求下降阶乘幂的时候因为这题的模数不是质数所以不能快乐求逆元但是因为kkk比较小所以直接暴力一波一个一个数乘这堆数中必定有一个是j1j1j1的倍数所以可以直接先除再乘就好了注意判断的时候每次都取模判断的话会愉快T掉所以应该在一开始的时候先把余数算出来然后根据余数的加法定理直接判就好了
参考博客https://www.cnblogs.com/yoyoball/p/9204846.html
