神仙数论题（
首先上手推式子，考虑枚举 gcd，有 ∏x1,x2,…,xn≤m(lcmni=1xi)gcdni=1xi=m∏d=1(∏x1,x2,…,xn≤⌊md⌋(lcmni=1xi)[gcdni=1xi=1])ddd∑x1,x2,…,xn≤⌊md⌋[gcdni=1xi=1]
考虑设 f(m)=∏x1,x2,…,xn≤m(lcmni=1xi)[gcdni=1xi=1]
和 g(m)=∑x1,x2,…,xn≤m[gcdni=1xi=1]
则 ∏x1,x2,…,xn≤m(lcmni=1xi)gcdni=1xi=m∏d=1fd(⌊md⌋)dd⋅g(⌊md⌋)
先考虑 g，设 gd(m)=∑x1,x2,…,xn≤m[gcdni=1xi=d]
则显然有 gd(m)=g(⌊md⌋)
以及 m∑d=1gd(m)=mn
于是有 g(m)=mn−m∑d=2g(⌊md⌋)
故可以使用类似杜教筛的方式在 O(n3/4) 的时间内求出所需的 g 值。
考虑 f，设 fd(m)=∏x1,x2,…,xn≤m(lcmni=1xi)[gcdni=1xi=d]
则显然有 fd(m)=f(⌊md⌋)dg(⌊md⌋)
以及 m∏d=1fd(m)=∏x1,x2,…,xn≤mlcmni=1xi
此时考虑设 h(m)=∏x1,x2,…,xn≤mlcmni=1xi
则有 f(m)=h(m)(m∏d=2f(⌊md⌋)dg(⌊md⌋))−1
考虑如何求 h。
注意 lcm 和 gcd 的本质：对所有数的每个质因子的指数取 max / min 并乘起来。
注意到，此题中同为乘，那么可以考虑对所有质因子同时做 min-max 容斥。
即 h(m)=∏x1,x2,…,xn≤m∏T⊆S(gcdi∈Txi)(−1)|T|+1 (S=[1,n]∩Z)
考虑枚举 gcd 并计算贡献，设 st(m)=∑x1,x2,…,xn≤m∑T⊆S[gcdi∈Txi=1](−1)|T|+1∏i∈T[xi≤t]
则有 h(m)=m∏d=1ds⌊m/d⌋(m)
设 st,d(m)=∑x1,x2,…,xn≤m∑T⊆S[gcdi∈Txi=d](−1)|T|+1∏i∈T[xi≤t]
显然有 st,d(m)=s⌊td⌋(m)
以及 t∑d=1st,d(m)=n∑k=1(nk)tkmn−k(−1)k+1
注意到这很像二项式展开的形式，考虑化一化 n∑k=1(nk)tkmn−k(−1)k+1=n∑k=0(nk)tkmn−k(−1)k+1−(n0)t0mn(−1)1=mn+n∑k=0(nk)tkmn−k(−1)k+1=mn−n∑k=0(nk)tkmn−k(−1)k=mn−n∑k=0(nk)(−t)kmn−k=mn−(m−t)n
故 st(m)=mn−(m−t)n−t∑d=2s⌊td⌋(m)
求 f,g,h,s 的总复杂度瓶颈在于 h 和 s —— 相当于使用了数论分块套数论分块套数论分块，而其他部分带快速幂的 log，故复杂度是 O(m7/8+m3/4logn) 的。
然而注意到要求得答案，实际上还需要求出 m∏d=1dd，而其中的 m 取 O(√n) 种值。
考虑先求 m∏d=1dm−d+1 再除 (m!)m+1。
注意到 m∏d=1dm−d+1=m∏d=1m∏i=dd=m∏i=1i∏d=1d=m∏i=1i!，所以可以预处理阶乘。
代码：
1 |
|