DZY Loves Math

DZY Loves Math

对于正整数 $n$，定义 $f(n)$ 为 $n$ 所含质因子的最大幂指数。

例如 $f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0$

给定正整数 $a,b$，求 $ \sum_{i=1..a} \sum_{j=1..b} {f(gcd(i,j))}$。

Sol

根据莫比乌斯反演可以得出

 $ \sum_{i=1..a} \sum_{j=1..b} {f(gcd(i,j))}$

=$\sum_{d} g[d]  \lfloor n/d \rfloor  \lfloor m/d \rfloor $

 其中 $g[d]=\sum_{d} \mu[d]*f[n/d]$

 后面整数分块，主要问题再求g

我们假设当前求g[x].

先考虑所有质因子次数都是一样的c，那么f[n/d]只有c和c-1两种取值，其中c-1仅在所有质因子出现一次时取到。

那么这时的答案是

-1  n有奇数个质因子

1   n有偶数个质因子

0   n=1

如果x的所有质因子的有任意一对次数不一样，那么g[x]=0.

因为如果次数

考虑怎么判断一个数的质因子次数是不是都一样

记a[x]表示x的最小质因子，b[x]表示a[x]的次数。

转移时类似dp

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！