求助整数分块
查看原帖
求助整数分块
147670
金珂拉楼主2021/9/28 18:11

第三种情况的分子部分处理的时候我用欧拉反演搞出了这个东西：

∏ddφ(d)⌊Ad⌋⌊Bd⌋⌊Cd⌋((Ad)!)φ(d)⌊Bd⌋⌊Cd⌋\prod_dd^{\varphi(d)\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor}((\frac{A}{d})!)^{\varphi(d)\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor}

整理了一下之后变成：

(∏ddφ(d)⌊Ad⌋⌊Bd⌋⌊Cd⌋)×(∏d((Ad)!)φ(d)⌊Bd⌋⌊Cd⌋)(\prod_dd^{\varphi(d)\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor})\times(\prod_d((\frac{A}{d})!)^{\varphi(d)\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor})

前半可以预处理 dφ(d)d^{\varphi(d)} 的前缀积，但是后半部分要怎么解决？

（题解好像这个地方没有用欧拉反演的……）

2021/9/28 18:11