（FJWC2020）DTOJ 4695. lg

本文主要是介绍（FJWC2020）DTOJ 4695. lg，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

有两个正整数 $n$ 和 $m$。
我们考虑所有长度为 $n$，每个元素在 $[1,m]$ 的整数序列。对于所有整数序列，设 $lcm$ 为这个序列中元素的最小公倍数，$gcd$ 为这个序列中元素的最大公约数，我们希望求出 $lc{m}^{gcd}$。你需要对于所有这些整数序列，计算 $lc{m}^{gcd}$ 之积 $mod998244353$。
即，我们需要计算 $({\prod }_{x_1,x_2,...,x_n\in [1,m]}lcm(x_1,x_2,...,x_n{)}^{gcd(x_1,x_2,...,x_n)})mod998244353$。

$Subtask1(10pts)$：$n,m\le 5$。
$Subtask2(20pts)$：$n,m\le 50$。
$Subtask3(10pts)$：$n,m\le 500$。
$Subtask4(20pts)$：$n,m\le 50000$。
$Subtask5(20pts)$：$n,m\le 200000$。
$Subtask6(20pts)$：$n\le 10^8,m\le 200000$。

题解

由于求的是乘积，且lcm会很大，故单独考虑每一个质因数的贡献，即枚举$p^q$，计算$p^q\le lcm$的数列的$gcd$的和。
显然$p^q\le lcm$不好算，而$p^q>lcm$较好算，于是容斥，计算$p^q>lcm$的数列的$gcd$的和时，需枚举$gcd$，而这个$gcd$可能与$p^q$有公约数，不方便计算，需要枚举公约数为$p^a$，然后直接像计算总答案那样反演即可，$a=0$时用整除分块，$a>0$时直接枚举，效率为$O(mlo{g}^{2}m+m\sqrt{n})$。

这篇关于（FJWC2020）DTOJ 4695. lg的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---