这场模拟赛的 T2 全场只有我一个人切了，还蒟了个 rk3，并且平生第一次在腾讯会议里给大家讲题。不过另外两题都不会，T1 三维偏序不会写，就不在模拟赛题解汇总里写了。
给定 (n,m)，求对于所有 (m^n) 种序列 (x) 满足 (x_iin[1,m])，它们的 (mathrm{lcm}(x_i)^{gcd(x_i)}) 的积。
(nleq 10^8,mleq 2 imes10^5)。
底数是 lcm。这就很不好搞。第一，多个数的 lcm 会很大很大，无法枚举；第二，lcm 不能像 gcd 一样好反演掉；第三，两个数的 lcm 等于两数乘积除以 gcd，但是多个数的 lcm 无法与 gcd 取得直接联系。但我们注意到，把 lcm 分解质因数后，每个质因数的幂都是 (leq m)，这个是显然的，而要求的又是个 (prod)，故可以把每个质因数的幂 (p^k) 分开来单独贡献。这大概是面对多个数 lcm 的一个有力武器吧。
于是 (p^k) 对答案的贡献肯定就是 (p^k) 的多少次方，而这个多少呢，就是所有满足 lcm 质因数分解式中包含 (p^k) 的序列 (x) 的 gcd 之和。也就是 (x) 中所有数的 (p) 的指数的 max 要恰好等于 (k)。而这个 max 恰好等于某数这玩意呢，有个套路，就是你先求 max 小于等于某数，然后差个分就完事了。好处在于，max 小于等于某数可以转化为每个数小于等于某数，就把限制给独立开来了，就很好搞。我们考虑设集合 (S) 为 ([1,m]) 中所有包含质因子 (p) 个数 (leq k) 的数，那么就是求 (G=sumlimits_{x_iin S}gcd(x_i))。对这个式子我们考虑反演一波（都是传统艺能就不做解释了）：
接下来为了方便起见，我们设一个记号：(S[x]) 表示 (S) 中所有 (x) 的倍数除以 (x) 所构成的集合。
这样子就得到一个很简洁的式子。那么此时已经有了一个 (Omega!left(m^2 ight)) 的朴素做法：枚举 (p^k)（(mathrm O(m))），然后按照 (G) 的最终式子枚举 (o=1sim m) 累加（因为 (o>m) 贡献显然为 (0)），然后 (|S[o]|) 这东西可能需要调和级数处理，带个 log 什么的。
然而我们这里的 (G) 的求法是针对任意普遍的 (S) 都成立的，而我们这里的 (S) 有特殊构造，考虑利用这一点来优化。(S) 显然是 (left{xin[1,m]mid p^{k+1} mid x ight})，那么 (|S[o]|) 这东西考虑能不能更好地表示？就是 ([1,m]) 内 (o) 的倍数去掉那些还是 (p^{k+1}) 倍数的，就是 (dfrac mo-dfrac{m}{mathrm{lcm}!left(o,p^{k+1} ight)})（以下不加整除号都代表下取整），即 (dfrac mo-dfrac{dfrac{mgcd!left(o,p^{k+1} ight)}{p^{k+1}}}{o})。而此时依然不能整除分块，因为虽然分母一样了，但是第二项的分子还是关于 (o)。不过发现唯一变化的这个 gcd 其实只有 (k+2) 种取值，是 log 级别的，所以可以大胆枚举。设当前枚举的是 (p^q)，那么贡献就是 (sumlimits_{gcdleft(o,p^{k+1} ight)=p^q}!left(dfrac mo-dfrac{dfrac{mp^q}{p^{k+1}}}{o} ight)^nvarphi(o))。此时依然不太方便整除分块，因为这个 (o) 不连续；奈何我想到了更好的方法。这个对这玩意处理的方法我认为是本题最怪的部分，我当时考场上不知道怎么就想到了。
你考虑分成 (oleqdfrac{mp^q}{p^{k+1}}) 和 (o>dfrac{mp^q}{p^{k+1}}) 两类分开贡献，两类各有福利。对前者，注意到 (gcd!left(o,p^{k+1} ight)=p^q) 的一个必要条件是 (p^qmid o)，而 (dfrac{mp^q}{p^{k+1}}) 以内 (p^q) 的倍数只有 (dfrac{mp^q}{p^{k+1}}/p^q) 这么多，而这个 (p_q) 恰好就约掉了！！！那么直接枚举的话，对复杂度的贡献就是 (mathrm O!left(dfrac{m}{p^{k+1}} ight))，稍后可以用调和级数分析法来均摊掉。对后者，显然 (dfrac{dfrac{mp^q}{p^{k+1}}}{o}=0)，只需要计算 (left(dfrac mo ight)^nvarphi(o)) 的贡献和。可以发现这仅关于 (o)，不难想到预处理。如何预处理呢？把 (gcd!left(o,p^{k+1} ight)=p^q) 这玩意变个形式得到 (p^qmid o,p^{q+1} mid o)（当然如果 (q=k+1) 则没有后面这个条件，不过这就更简单了），就类似差分一下，发现只需要求 (o>?,??mid o) 的贡献和。那你考虑把每个数的倍数的贡献序列调和级数预处理下来，查询的时候在里面二分即可。
来分析一下复杂度。第一类对复杂度的贡献，对每个 (p^{k+1}) 会被算 log 次，如果只算一次的话是调和级数复杂度（1log），算 log 次就是 2log；第二类就很显然了吧，二分 log 次就是 2log。所以总体 2log，理论能过。并且非常跑不满，毕竟能表示成质数的整次幂 (p^k) 的数分布还是很稀疏的。