noip竞赛数学基础.ppt

数学根底题目

1~n的素数假设要求1~100的素数–2是素数,删除2*2,2*3,2*4,…,2*50–第一个没被删除的是3,删除3*3,3*4,3*5,…,3*33–第一个没被删除的是5,删除5*5,5*6,…5*20?得到素数p时,需要删除p*p,p*(p+1),…p*[n/p],运算量为[n/p]-p,其中p不超过Sqrt〔n〕(想一想,为什么)

素数相关问题和素数有关的问题?如何求1~n的所有素数??如何判断一个数n是否为素数??如何求两个数的最大公约数??如何给一个数n分解素因数?

素数判定枚举法:O(n1/2),指数级别改进的枚举法:O(phi(n1/2))=O(n1/2/logn),仍然是指数级别概率算法:Miller-Rabin测试+Lucas-Lehmer测试

Miller-Rabin测试a^s≡1(modn),或者素数对于所有a通过测试,合数通过测试的概率不超过1/4只测试a=2,3,5,7,那么2.5*10^13以内唯一一个可以通过所有测试的数为3215031751

区间内的素数给出n,m(n=10^6,m=10^5),求n~n+m之间的素数有多少个哪种方法快?筛还是依次素数判定?

最大公约数

方法一:使用惟一分解定理,先分解素因数,然后求最大公约数方法二:(Euclid算法)利用公式gcd(a,b)=gcd(b,amodb),时间复杂度为O(logb)?方法三:(二进制算法)假设a=b,gcd(a,b)=a,否那么–A和b均为偶数,gcd(a,b)=2*gcd(a/2,b/2)–A为偶数,b为奇数,gcd(a,b)=gcd(a/2,b)–如果a和b均为奇数,gcd(a,b)=gcd(a-b,b)?不需要除法,适合大整数

扩展GCD(最大公约数)?一定存在整数x,y，使得ax+by=gcd(a,b)Functionext_gcd(a,b:int;varx,y:int):int;Beginifb=0thenbeginx:=1;y:=0;exit(a);end;ext_gcd:=ext_gcd(b,amodb,y,x);dec(y,(adivb)*x);End;?由数学归纳法可证明ax+by=gcd(a,b),满足ax+by=d的数对(x,y)不是惟一的,因为当x增加b且y减少a时和不变。

天平有一些砝码,重量为1,3,9,27,81…形如3^k,每个重量砝码只有一个.任意给一个重量为m的物体,把它放在天平左边,如何把放置砝码使得天平平衡?放在左边或者右边都可m=10^100〔mod3、9、…=0、1、2〕？

Euler定理欧拉函数:1~n中和n互素的元素个数?(n)?Euler定理假设gcd(a,n)=1那么a?(n)≡1(modn)?意义：当b很大时ab≡abmod?(n)(modn)，让指数一直比较小?欧拉函数是积性函数，即当(m,n)=1时f(mn)=f(m)*f(n)

线性同余方程ax≡b(modn)?扩展的Euclid算法–存在整数y，使得ax-ny=b–记d=(a,n)，a’=a/d,n’=n/d，必须有d|b–a’x-n’y=1*(b/d)–注意：x不唯一,所有x相差n/d的整数倍

整数序列

{A1,…,An}、B、P求{X1,…,Xn}使得A1*X1+…+An*Xn=B(modP)

染色方案N*M(N=10^100,M=5)的格子纸，每个格子被填上黑色或者白色。求没有任何一个2*2的格子同色的染色方案总数modP。？？

分析每行最多32(=2M)种状态?任两种状态是否可组成相邻行，可以用一个32*32的矩阵S表示?下面证明Sk的元素(i,j)表示以i为第一层,j为最后一层,共k+1层的方法数?K=0时显然成立,考虑Sk=Sk-1*S,任何一个元素SK(i,j)=sum{SK-1(i,x)*S(x,j)},乘法原理?因此Sn的所有的元素之和就是答案

灯泡有n(=10^6)个灯排列成环形.每个单位时间,灯i改变状态当且仅当上一个时刻它下一个灯(in时为i+1,i=n时为1)开着.给n个灯的初始状态以及m(m=10^9),给出m时间单位以后的状态.

分析算法一:直接模拟O(nm)?算法二:事先计算循环节,那么时间复杂度和m无关,上限是O(n2^n),但具体运行时间不好估计算法三:第一次a[1,i]=a[0,i]