题目所求即
\[\prod_{i=1}^n\prod_{j=1}^mf_{gcd(i,j)} \]由于没有出现\([gcd(i,j)=1]\)，所以枚举\(gcd\)强行凑（下面对乘积的强行凑记住），原式就等于
\[\prod_{d=1}^{min(n,m)}\prod_{i=1}^n\prod_{j=1}^mf_{gcd(i,j)}^{[gcd(i,j)=d]}=\prod_{d=1}^{min(n,m)}\prod_{p=1}^{\frac{n}{d}}\prod_{q=1}^{\frac{m}{d}}f_{d}^{\sum_{k|gcd(p,q)}u(k)}=\prod_{d=1}^{min(n,m)}f_{d}^{\sum_{p=1}^{\frac{n}{d}}\sum_{q=1}^{\frac{m}{d}}\sum_{k|gcd(p,q)}u(k)}=\prod_{d=1}^{min(n,m)}f_{d}^{\sum_{k=1}^{min(\frac{n}{d},\frac{m}{d})}u(k)\frac{n}{dk}\frac{m}{dk}} \]这个时候发现分块套分块会超时，所以使用莫比乌斯反演第二形式，令\(T=dk\)并优先枚举\(T\)，则原式等于
\[\prod_{d=1}^{min(n,m)}f_{d}^{\sum_{d|T}u(\frac{T}{d})\frac{n}{T}\frac{m}{T}}=\prod_{T=1}^{min(n,m)}\prod_{d|T}f_d^{u(\frac{T}{d})\frac{n}{T}\frac{m}{T}}=\prod_{T=1}^{min(n,m)}(\prod_{d|T}f_d^{u(\frac{T}{d})})^{\frac{n}{T}\frac{m}{T}} \]令\(F(T)=\prod_{d|T}f_d^{u(\frac{T}{d})}\)，则原式等于
\[\prod_{T=1}^{min(n,m)}F(T)^{\frac{n}{T}\frac{m}{T}} \]预处理\(F\)后分块即可
标签：frac,gcd,表格,min,sum,原式,prod,数字 From： https://www.cnblogs.com/dingxingdi/p/18175983