[SDOI2017] 数字表格
Identity_Equation
·
·
个人记录
下文中默认m \le n
\prod_{i=1}^n\prod_{j=1}^mf(gcd(i,j))
=\prod_{i=1}^n\prod_{j=1}^m\prod_{d=1}f(gcd(i,j))[gcd(i,j)=d]
=\prod_{i=1}^n\prod_{j=1}^m\prod_{d=1}f(d)[gcd(i,j)=d]
=\prod_{d=1}f(d)^{\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]}
=\prod_{d=1}f(d)^{\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[gcd(i,j)=1]}
=\prod_{d=1}f(d)^{\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{t|gcd(i,j)}\mu(t)}
=\prod_{d=1}f(d)^{\sum_{t=1}\mu(t)\sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{dt} \rfloor}1}
=\prod_{d=1}f(d)^{\sum_{t=1}\mu(t)\lfloor \frac{n}{dt} \rfloor\lfloor \frac{m}{dt} \rfloor}
=\prod_{d=1}(\prod_{t=1}^{\lfloor \frac{n}{d} \rfloor}f(d)^{\mu(t)})^{\lfloor \frac{n}{dt} \rfloor\lfloor \frac{m}{dt} \rfloor}
=\prod_{d=1}\prod_{t=1}^{\lfloor \frac{n}{d} \rfloor}f(d)^{\mu(t)\lfloor \frac{n}{dt} \rfloor\lfloor \frac{m}{dt} \rfloor}
令T=dt
=\prod_{T=1}\prod_{d|T}f(d)^{\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor}
=\prod_{T=1}(\prod_{d|T}f(d)^{\mu(\frac{T}{d})})^{\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor}