Codeforces Alternating Sum-逆元简单题

回顾一下信息安全中讲的数论中关于逆元的概念。首先关于取模这个操作呢,加减乘都是封闭的,比如8+11=((8%17)+(11%17))%17=2,19+21=((19%17)+(21%17))=6,乘法也是,可以先模再乘,乘完再模,其意义不会变化。而除法就不一样了,计算a/b≡?(mod m),我们是不能先计算a(modm)再/b的,比如15/3≡1(mod4) 那我们该如何计算除法的取模操作呢?

此时就需要引入乘法逆元的概念了

定义 对a∈Zm,存在b∈Zm,使得a×b ≡ 1 (mod m),则b为a的乘法逆元 ,记b=1/a

这个数学概念的引入其实是非常自然的,比如我们计算整数的除法x/y,我们可以用x*(1/y),这个1/y我们称之为y的倒数。因此乘法逆元我们也可以认为是取模的倒数。如何计算逆元呢?主要有三种方法,一种是扩展欧几里得,一种是利用费马小定理,还有一种是递推法。

费马小定理如下:

$$a^p-1\equiv1(mod p)$$, p为素数

很直观的一个解释:我们的目标是求 1/b ≡ ? (mod m),那么由b* b^p-2 ≡ 1(mod p),所以我们可以容易得到结论:b关于p的逆元就是b^p-2. 所以我们可以用快速幂在O(logp)的时间内进行求解。

第二种方法是扩展欧几里得,扩展欧几里得(EXGCD)算法可以在 O(log max(a, b))的时间内求出关于 x、y的方程
ax + by = gcd(a, b)
的一组整数解

当 b 为素数时, gcd(a, b) = 1,此时有
ax + by = 1

时间复杂度是O(loga)

代码

递推法的思想则是预处理出1..p-1所有关于p的模数。

设 p=k×i+r,( r<i, 1<i<p),则有
$$k*i+r\equiv0 (mod p) $$

两边同时乘上 r ^ {-1} + i ^ {-1} ,得
$$k*r^{-1}+i^{-1}\equiv0(mod p)$$

移项,得
$$i^{-1}\equiv-k*r^{-1}(mod p)$$


$$i^{-1}\equiv-[\frac{p}{i}]*(p mod i)^{-1} (mod p)$$

我们可以利用这个式子进行递推,边界条件为1^-1≡1(mod p),时间复杂度为 O(n).

代码:

最后,我们发现之前的三种方法都是对于模数为素数而言的,那么如果mod不是素数呢?方法如下(前提是b|a):

《Codeforces Alternating Sum-逆元简单题》

证明如下:
《Codeforces Alternating Sum-逆元简单题》

注意的是,对于大多数情况我们并不能用这个方法,因为我们在做题的时候,分子和分母通常是非常大的,所以可能中间操作就引入了很多取模操作,就不会有b|a这样的条件,但此时还是可以通过之前的三个方法计算b的逆元计算出值的。

回到题目中的例题,题目的大意就是求下面的一个值:

$$\sum_{i=0}^{n} s_ia^{n-i}b^{i}mod(10^{9}+9) \qquad$$

其中si是一个周期为k的数列。另外还有一个重要的条件就是k | n+1.

解法就是直接求出这个序列1..k的值,然后后面的都是前面的这个值的等比序列,比是(b/a)^k, 总共的序列数(n+1)/k。注意要特别讨论一下a=b的情形,否则等比数列求和的q=1当然我做题目的时候脑残地没有看到k | n+1的条件,直接用a^n+a^n-1b+…b^n=(a^n+1+b^n+1)/(a-b)的条件按照模数为i进行分片计算,被自己蠢到不行。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注