BZOJ 1128 [POI2008]Lam


题目链接: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,维护一个高精度取低精模即可。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1128 [POI2008]Lam


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,