Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

一个不用逆元也不用二分求和的思路

Posted by shengrang at 2015-09-05 11:15:59 on Problem 1845

.. 拿费马小定理水过了..

大概就是在算(1 + p1^1 + p1^2 + ... + p1^r) % M.的时候

p1 ^ (M-1) == 1 (mod M)
设x = (r+1) / 9900, y = (r+1) % 9900

所以只要计算出m = (1 + p1^1 + p1^2 + ... + p1^(M-2)) % M 和 n = (1 + p1^1 + p1^1 + ... + p1^ (y-1)) % M就行了..


答案就 x * m + n  % M;  还挺快, 0MS水过的

Followed by:

Post your reply here:

Home Page Go Back To top