【题解】洛谷P5431 乘法逆元2

题目

洛谷P5431 乘法逆元2

题解

警告:此题解时间复杂度正确,但代码缺少底层常数优化,因此运行较慢,无法通过全部的测试。

此题如果直接求每个数的逆元会超时。设 ,易知:

预处理出a[i]的前缀积、后缀积和逆元积,就可快速求单个数的逆元。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月26日 下午3:20

【小白解析】
此题解题思路较为简单粗暴,主体逻辑继承数学思想,故不多赘述。
第9至12行是老生常谈的快速读取,(s<<3)+(s<<1)等同于s*8+s*2,也就是在十进制下将s右移一位。ch^48相当于让ch与’0’做异或运算,得出ch对应的数字值。
s1[i]==Πaj (0<=j<=i),即a[0]*a[1]*…*a[i];s2[i]则以相反的方式储存,等同于a[0]*a[1]*…*a[n-i+1]。s1[i-1]和s2[i+1]分别构成ai的前缀积与后缀积。