北京大学暑期课——ACMICPC课程介绍.pdf

北京大学暑期课《ACM/ICPC竞赛训练》

信息科学技术学院《程序设计与算法》

ACM/ICPC中的数学

郭炜/林舒

2

一些数论基本定理

(a+b)modc=

((amodc)+(bmodc))modc

(a*b)modc=

((amodc)*(bmodc))modc

3

一些数论基本定理

消去律：若gcd(c,p)=1,则

ac≡bcmodp=a≡bmodp

4

一些数论基本定理

消去律证明：

ac≡bcmodp=ac=bc+kp=

c(a-b)=kp

c和p没有除1以外的公因子=

1)c能整除k或2)a=b

如果2不成立，则c|kp

c和p没有公因子=c|k，所以k=ck

=c(a-b)=kp可以表示为c(a-b)=ckp

因此a-b=kp，得出a≡bmodp

5

快速幂取模

intPowMod(inta,intb,intc)

{//快速求a^b%c，要避免计算中间结果溢出

intresult=1;

intbase=a%c;

while(b){

if(b1)

result=(result*base)%c;

base=(base*base)%c;

b=1;

}

returnresult;

}

6

等比数列二分求和取模

2n

S=a+a+...+a

n

要求Smodp

n

如果用公式算，可能溢出，因此用二分法求

1)若n是偶数

S=a+...+an/2+an/2+1+an/2+2+...+an/2+n/2

n

n/2n/2n/2

=(a+...+a)+a(a+...+a)

=S+an/2S

n/2n/2

=(1+an/2)Sn/2

7

等比数列二分求和取模

2)若n是奇数

S=a+...+a(n-1)/2+a(n-1)/2+1+...

n

+a(n-1)/2+(n-1)/2+a(n-1)/2+(n-1)/2+1

=S(n-1)/2+a(n-1)/2(a+...+a(n-1)/2)+an

=(1+a(n-1)/2)S(n-1)/2+an

8

等比数列二分求和取模

intPowSumMod(inta,i