number theory数论研究整数性质,是数学一门重要分支

偏向于应用,但理论不失严谨胡渊 数论与信息学竞整胡渊 数论与信息学竞m为商0r<b为余数(ramod胡渊胡渊 数论与信息学竞整除的⇐⇒胡渊 数论与信息学竞胡渊胡渊 数论与信息学竞,,,一大类,, ?胡渊 数论与信息学竞胡渊胡渊 数论与信息学竞如果一个大于1的数的约数只有1和其本身,则称其为质数. (a,b)如果两个数没有大于一的公约数,即 (a,b)=1,则称a,b互质,记作a⊥b欧几里得.+,b即最大公约数相同取n=−bac则有a+nb=amodb.b (b,amod,为O(logmax(a,b)).(代码?)胡渊 数论与信息学竞胡渊胡渊 数论与信息学竞x2≡1(modP)→x≡±1(modP质因子,,胡渊 数论与信息学竞胡渊 数论与信息学竞简胡渊 数论与信息学竞,,,,为a的逆元,记作a−1幂,a−1≡aP−2(modP)),炫耀数论知识等胡渊 数论与信息学竞费马小定理胡渊 数论与信息学竞有{a2a(P1)a}两两不同余于是其在modP意义下即(P1)!aP−1(P1)!(modP)两边消去(P1)!,定理得证胡渊 数论与信息学竞胡渊 数论与信息学竞利用费马小定理配合快速幂,很容易求出一个整数的逆元时间杂度为O(nlogP)bP/ici=P−PmodbP/ici≡−Pmodi(modP−bP/ic(Pmodi)−1≡i−1(modP从小到大计算i1时由于Pmodii,其逆元已经算出胡渊 数论与信息学竞Wilson胡渊 数论与信息学竞如果P是质数有(P11(modP证明思路:P5时,(P1)!中去掉1和P1,别的项总可以和,胡渊 数论与信息学竞质数胡渊 数论与信息学竞显然每个合数n都存在一个≤√n的因子直接枚举这个因子可.是否是质数.对于一个给定的数P(不一定是质数),随机一个在[2P−1)的数利用快速幂判断是否有aP−1modP=反例:2340≡1(mod341)反例确实不多,但是不能忽略胡渊 数论与信息学竞Miller-Rabin素数判胡渊 数论与信息学竞,对于可能的P选定一些a[2P1),假设P1=2Kr,其中如果P为质数则a2KrmodP=1,根据判断题有a2K1rmodP=±1.类似的,对于k[0K),都可以做这个判断如果a2k1rmodP=1a2krmodP6=±1则可推出P质数.具体计算时只要先算出armodP然后不断平方时间复杂度仍然为O(logP)生成范围内所有 胡渊 数论与信息学竞,),,法O(nlog胡渊 数论与信息学竞补充知识:积性胡渊 数论与信息学竞胡渊 数论与信息学竞补充知识:积性胡渊 数论与信息学竞,,胡渊胡渊 数论与信息学竞关键问题是求出φ(pq)的值成pqpq−1(为什么经典P P i j i j=1

(i,j给定整数n，求1≤x,y≤n且 1n+2n+...+P

Pb=1Blcm(a,b) 胡渊 数论与信息学竞墨墨的 究a1x1+a2x2++anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N,an,B的取值范围，求出有多少B N≤12,0≤ai≤4×10,1≤Bmin≤Bmax≤胡渊 数论与信息学竞胡渊胡渊 数论与信息学竞 则2x和3x不能在该子集中。 胡渊 数论与信息学竞 ，火星人要jyy用飞船上的瓶子来换.jyy的飞船上共有N个瓶子1≤N≤1000，经过协商，火星人只要其中料给jyy.为Vi(Vi为整数,并且满足1≤Vi≤ ).火星人并不会把 来交差.jyy当然知道他们会来这一手,于 胡渊 数论与信息学竞a0+a1x+a2x2+...+anxn=

≡

(modPnmmodPnO(nm)−O(n)−O(P2)−O(logPn,m,P≤例题:离散对给定质数Pab求满足axb(modP)的最小的x.根据费马小定理有x[0P2).计算O(P)不好意思,P=1014胡渊 数论与信息学竞给定nn一次询问:O(√n

i

nbi−≤补充知识:求离散对数的大步小步算取一个接近P√数M,x显然具有sM+r的形式 得asM+r≡b(modP有arba−sM(modP)对于r[0M)将结果存在Hash表中这样做复杂度O(PlogP胡渊 数论与信息学竞胡渊 数论与信息学竞扩展知识