BZOJ 1128 [POI2008]Lam

发布于 2017-11-03  171 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1128

题意:对于一个长度为 n 的数列 p,数列中任意两个数互质。准备一个无限长的储存器。然后从 p1 开始,把储存器中 p1 倍数位置都赋值为 p1,把储存器中 p2 倍数位置都赋值为 p2,把储存器中 p3 倍数位置都赋值为 p3。把储存器中 pn 倍数位置都赋值为 pn。最后求每个 pi 在储存器中出现的比例,用分数表示。


这种覆盖的问题一般倒着考虑,即\(A_i=A_{i+1} \cdot \frac {P_{i+1}-1}{P_i}\)

高精度维护分数即可,考虑到暴力求 gcd 太麻烦了,实际上我们只需要求分子和\(P_i\) 的 gcd,维护一个高精度取低精模即可。

 


一个非常弱的准退役OIER