对除法的模逆元处理:
因为 109+710^9 + 7109+7 是质数,我们可以使用费马小定理来计算除以 6 的模逆元。即:
a/6≡a∗inv(6)modMODa / 6 ≡ a * inv(6) mod MODa/6≡a∗inv(6)modMOD,
其中 inv(6)=6(MOD−2)modMODinv(6) = 6^{(MOD - 2)} mod MODinv(6)=6(MOD−2)modMOD。
计算:
MOD=109+7MOD = 10^9 + 7MOD=109+7
inv6=pow(6,MOD−2,MOD)inv6 = pow(6, MOD - 2, MOD)inv6=pow(6,MOD−2,MOD)
然后:
S=m∗(m+1)∗(2m+1)/6modMODS = m * (m + 1) * (2m + 1) / 6 mod MODS=m∗(m+1)∗(2m+1)/6modMOD
可以表示为:
S = (m * (m + 1) % MOD) * ((2m + 1) % MOD) % MOD * inv6 % MOD
By signing up a 星高度 universal account, you can submit code and join discussions in all online judging services provided by us.
Using your 星高度 universal account