首页 > 其他分享 >最大幂指数 题解

最大幂指数 题解

时间:2024-04-20 23:25:10浏览次数:27  
标签:lfloor mu right 最大 题解 sum rfloor 幂指数 left

Statement

\(f(x)\) 表示 \(x\) 所含质因子的最大幂指数,对于 \(T=10^4\),\(a,b\le10^7\),求

\[ \sum_{i=1}^a\sum_{j=1}^bf(\gcd(i,j)) \]

时限 2s

Solution

\[ \begin{aligned} &\sum_{i=1}^a\sum_{j=1}^bf(\gcd(i,j))\\ =&\sum_{i=1}^a\sum_{j=1}^b\sum_{d=1}^{\min(a,b)}[d=\gcd(i,j)]f(d)\\ =&\sum_{d=1}^{\min(a,b)}f(d)\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d]\\ =&\sum_{d=1}^{\min(a,b)}f(d)\sum_{i=1}^{\left\lfloor\frac ad\right\rfloor}\sum_{j=1}^{\left\lfloor\frac bd\right\rfloor}[\gcd(i,j)=1]\\ =&\sum_{d=1}^{\min(a,b)}f(d)\sum_{i=1}^{\left\lfloor\frac ad\right\rfloor}\sum_{j=1}^{\left\lfloor\frac bd\right\rfloor}\sum_{p\mid i\land p\mid j}\mu(p)\\ =&\sum_{d=1}^{\min(a,b)}f(d)\sum_{p=1}^{\min(\left\lfloor\frac ad\right\rfloor,\left\lfloor\frac bd\right\rfloor)}\mu(p)\left\lfloor\dfrac a{dp}\right\rfloor\left\lfloor\dfrac b{dp}\right\rfloor\\ =&\sum_{d=1}^{\min(a,b)}\sum_{p=1}^{\min(\left\lfloor\frac ad\right\rfloor,\left\lfloor\frac bd\right\rfloor)}f(d)\mu(p)\left\lfloor\dfrac a{dp}\right\rfloor\left\lfloor\dfrac b{dp}\right\rfloor\\ =&\sum_{k=1}^{\min(a,b)}\left\lfloor\dfrac ak\right\rfloor\left\lfloor\dfrac bk\right\rfloor\sum_{d\mid k}f(d)\mu\left(\frac kd\right) \end{aligned} \]

记 \(g(k)=\sum_{d\mid k}f(d)\mu(\frac kd)\),这就是后面一个 Sigma

若预处理出 \(g\) 的前缀和,这个式子就可以数论分块求

以上是自己想出的,属于基操。

1

因为对于 \(\gcd(x,y)=1\),有 \(f(xy)=\max(f(x),f(y))\)、\(\mu(xy)=\mu(x)\mu(y)\),我们觉得 \(g\) 没有积性,不好求

而 \(g(n)=\sum_{ab=n}f(a)\mu(b)\)

求完 \(f,\mu\) 后直接:

for (int b = 1; b <= n; ++b) if (mu[b]) for (int a = b; a <= n; a += b) g[a] += mu[b] * f[a / b];

经过实践这个计算量是 1e8 的,可以接受

为什么不是直接 \(n\ln n\) 的呢?因为只用到了 \(\mu(i)\not=0\) 的部分,这样的 \(i\) 只有 6e6 个

2

sto hunction orz

我们还是推一下 \(g\) 怎么求:

\[ g(p^\alpha)=f(p^\alpha)-f(p^{\alpha-1})=1 \]

而剩余 \(n=p_1^{\alpha_1}p_2^{\alpha_2}...\),当 \(\alpha_1=\alpha_2=\alpha_3=\cdots\) 时,

除了 \(\mu(p_1p_2p_3\cdots)f\left(\frac t{p_1p_2p_3\cdots}\right)=\alpha_1-1\) 之外,其他都是 \(\alpha_1\)

故 \(g(n)=(-1)^{m+1}\)

而 \(\alpha\) 不相等时易证 \(g(n)=0\)

标签:lfloor,mu,right,最大,题解,sum,rfloor,幂指数,left
From: https://www.cnblogs.com/laijinyi/p/18148390

相关文章

  • 一个人的数论 题解
    Solution令指数为\(k\)正常反演得到\[\sum_{d\midn}\mu(d)d^k\sum_{i=1}^{\fracnd}i^k\]设\(f(x)=\sum_{i=1}^xi^k\),它是一个关于\(x\)的\(k+1\)次多项式求这个多项式可以插值\(\mathcalO(n^2)\)(推荐)高斯消元(待定系数法)\(\mathcalO(n^3)\)直接伯努利数\(\ma......
  • 重建计划 题解
    题意:一棵树,有边权,求边权平均值最大且经过点数在\([L,R]\)的路径长度.Solution首先二分答案\(x\),每条边权减去\(x\)后问题转为求最大路径长度,若答案\(\ge0\)则可行1边分治保平安。先转二叉树,这里有两种方法:一种是像线段树一样建,另一种是普通贪心的建,反正都可以然后边......
  • 题解:P10365 [PA2024] Kraniki(评分:8.4)
    前言我们一场模拟赛的题,结果原题是新鲜出炉的。小弟不才,感觉这题是做过的题中几乎最复杂的了。既然搞懂了,就来写一发题解吧。(题外话:目前最优解,我的常数真是小小又大大啊)"Upanddown,glowin'round..."Solution1、一个经典的Trick直接模拟每一种情况显然不可取,考虑计算每......
  • 染色问题 题解
    \(f(i)\):满足\(n\)行\(m\)列每行每列都有颜色,最多用了\(j\)种颜色的方案数根据容斥原理\[f(i)=[(i+1)^m-1]^n-\sum_{i=1}^m(-1)^{k-1}C_m^k[(i+1)^{m-k}-1]^n\]意思是对于每一行,每个格子都可以填\(i\)种颜色或不填;但是整行不能一个格子都不填色,所以减一;而有\(n\)行,......
  • 俄罗斯方块 题解
    题意:矩阵checkmax、矩阵求max,checkmax的值一定比当前矩阵原max大外层线段树每个节点开一棵线段树,每个点记录列的max与checkmax的标记checkmax时:对路过的点的max更新,对完全包含的区间的checkmax标记更新求max时:对路上的checkmax与完全包含的max更新\((a,b......
  • P3281 数数 题解
    j带来的贡献:\(f[i]*b^{j-i}+\sum(i\cdot\text{num}[i+1..j])+pre_{j-i}\)\(\displaystyle\sum_{j=i+1}^n\left\{f[i]*b^{j-i}+i\cdot\dfrac{b^{j-i}(b^{j-i}-1)}2+pre_{j-i}\right\}\)\(\displaystyle\sum_{j=1}^{n-i}\left\{f[i]*b^j+i\cdot\dfrac{b^j(......
  • ABC350题解(E-G)
    E直接搜一下\(N\)的可能到达的值的个数,发现不多(大约\(10^4\)个),直接暴力dp(记忆化搜索)。转移式\(f_i=\max(X\log_{A}N,\dfrac{\sum\limits_{j=1}^6f_{i/j}}{6}+Y)\)。化简得到\(f_i=\max(X\log_{A}N,\dfrac{\left(\sum\limits_{j=2}^6f_{i/j}\right)+6Y}{5})\)。F文艺......
  • 荒岛野人 题解
    Statement有\(n(\le15)\)个野人,第\(i\)个野人的寿命是\(L_i(\le10^6)\)年。荒岛上有\(m\)个山洞排列成一个环,但你不知道\(m\)到底是多少。第\(i\)个野人第一年会从第一个山洞开始往后数\(C_i\)个住下来,此后每一年都会往后数\(P_i\)个山洞住下来。已知不会发生某......
  • 双模数问题 题解
    Statement\(S(n,m)=\{k\midk\in\mathbbN^+\landn\bmodk+m\bmodk\gek\}\),求\(\varphi(n)\varphi(m)\sum_{k\inS(n,m)}k\pmod{998244353}\)(\(n,m\le10^{15}\))Solution欧拉函数怎么求就不说了,可以\(\mathcalO(\sqrtn)\)解决\(n\bmodk+m\bmodk......
  • [HEOI2014]大工程 题解
    发现可以直接建立虚树。设\(dp_{u,0/1/2}\)表示第\(u\)个节点的子树内,所有选中节点到它的距离之和/选中节点中到它的最短距离/选中节点中到它的最长距离,\(as_{u,0/1/2}\)则代表对于这个子树,题目所问问题的三个答案,\(i1,i2\)分别为使\(dp_{u,1/2}\)取极值的\(v\)。则\(......