提高班第四讲初等数论.ppt

初等数论题 Presentedby汪演增 Achilles USC 目录 1 素数2 快速幂取模3 唯一质因子分解定理3 最大公约数 欧几里得算法 4 扩展欧几里得算法5 同余以及线性同余方程6 特殊的线性同余方程组 中国剩余定理 素数 1 判断n是否为素数 for inti 2 i i n i if n i 0 flag 1 break 2 如果要求10 6区间内的素数呢 概念 除了1和此整数自身外 不能被其他自然数整除的数 2 给定一个范围 求这个范围内的素数 进行如下步骤 0 从2开始 2是第一个素数 也是第一个新素数 取出2 1 筛掉所有新素数的倍数 2 留下来的数里面第一个 最小的 是新素数 取出这个新素数 3 重复1和2直到没有数存在 Eratosthenes筛法 memset flag 0 sizeof flag for inti 2 i i 1000000 i if flag i for intg i g 1000000 g i flag g 1 快速幂取模 1 10 8怎么求 3 10 10 8 9999 2 10 180呢 1 模取运算的性质 1 a b c a c b c c 2 a b c a c b c 10 int64fn int64a int64k 11 12 if k 0 return1 13 if k 1 returna mod 14 int64tmp1 fn a k 2 15 int64tmp2 tmp1 tmp1 mod 16 if k18 a k mod 快速幂 风格简洁 int64quickmod int64x int64n int64pw 1 while n 0 if n 质因子分解定理 唯一因子分解唯一质因子分解定理 合数a仅能以一种方式 写成如下的乘积形式 a p1e1p2e2 prer其中pi为素数 p1 p2 pr 且ei为正整数 那么怎么求的一个合数n的所有素因子呢 暴力法 1 先求出每一个n的素因子 然后穷举 筛选法的妙用 思路不明白没关系 看代码 for inti 2 i i n if n i 0 cout i while n i 0 n i elsei if n 1 cout n endl 其他一些关于约数的公式 初等数论的概念 除法定理 余数除法定理 对任意整数a和任意正整数n 存在唯一的整数q和r 使得a qn r 其中0 r n 值q成为除法的商 值r a modn 称为除法的余数 公约数与最大公约数d是a的约数并且也是b的约数 则d是a和b的公约数 两个不同时为0的整数a和b的最大公约数表示为gcd a b 互质数 如果两个整数a与b只有公因数1 即如果gcd a b 1 则a与b称为互质数 互素 定理 对任意整数a b和p 如果gcd a p 1且gcd b p 1 则gcd ab p 1 最大公约数gcd 最大公因子 Euclidean算法求两个正整数a和b的gcd 先令r0为a r1为b 接着执行如下运算 GCD递归定理 对任意非负整数a和任意正整数b gcd a b gcd b amodb 例 求8251和6105的最大公因数 8251 6105 1 21466105 2146 2 18132146 1813 1 3331813 333 5 148333 148 2 37148 37 4最后除数37是148和37的最大公因数 也就是8251与6105的最大公因数 欧几里德算法 辗转相除法 intgcd a b returnb gcd b a b a if b returna returngcd b a b LCM LeastCommonMultiple 有了GCD LCM就好办了LCM a b a b GCD a b 实际上最好写成a GCD a b b思考 为什么下面的写法好 扩展欧几里得算法 扩展欧几里得定理 对于不完全为0的非负整数a b gcd a b 表示a b的最大公约数d 必然存在整数对x y 使得gcd a b d ax by 扩展欧几里德算法是用来在已知a b求解一组x y使得ax by Gcd a b d 设a b 1 显然当b 0时 gcd a b a 此时x 1 y 0 2 ab 0时 设ax1 by1 gcd a b bx2 amodb y2 gcd b amodb 根据朴素的欧几里德原理有gcd a b gcd b amodb 则 ax1 by1 bx2 amodb y2 即 ax1 by1 bx2 a a b b y2 ay2 bx2 a b by2 根据恒等定理得 x1 y2 y1 x2 a b y2 这样我们就得到了求解x1 y1的方法 x1 y1的值基于x2 y2 上面的思想是以递归定义的 因为gcd不断的递归求解一定会有个时候b 0 所以递归可以结束 voidextend Eulid inta intb inttemp if b 0 x 1 y 0 q a q是什么 else extend Eulid b a b temp x x y y temp a b y 扩展欧几里得典型例题 POJ1061青蛙的约会 TIPS 抽象模型 建立方程就已成功了一半 根据题意 青蛙若想碰面的话 则必有 x mt y nt p L p为任意整数 方程化为 m n t y x pL 则有 m n t y x modL 0 即为 m n tmodL y x为线性同余方程 此方程有解当且仅当y x能被m n和L的最大公约数 记为gcd m n L 整除 即gcd m n L y x有解 这时 如果x0是方程的一个解 即当t x0时 m n tmodL y x成立 设d gcd m n L 根据扩展欧几里得定理 则必存在整数对 r s 使得 m n r L s d 则可得t r y x d scanf I64d I64d I64d I64d I64d 设m 0 若m a b 即a b km 则称a同余于b模m 记为a b关于模m同余的充要条件是整数a和b被同一正整数m除时 有相同的余数 同余 同余的性质 例 求3406写成十进位数时的个位数 根据题意是要求a满足3406 a mod10 显然32 9 9 mod10 34 1 mod10 从而3404 1 mod10 因此3406 3404 32 9 mod10 所以个位数是9 这个可以用我们之前学的的方法做吗 模的逆元 若m 1 a m 1 则存在c使得ca 1 modm 我们把c称为是a对模m的逆 记为a 1 modm 或a 1 求解模线性方程 定理 方程ax b modn 对于未知量x有解 当且仅当gcd a n b定理 方程ax b modn 或者对模n有d个不同的解 其中d gcd a n 或者无解 求解模线性方程 定理 假设方程ax b modn 有解 即有d b 其中d gcd a n x0是该方程的任意一个解 则该方程对模n恰有d个不同的解 分别为 xi x0 i n d i 1 2 d 1 求解模线性方程 定理 设d gcd a n 假定对整数x 和y 有d ax ny 如果d b 则方程ax b modn 有一个解的值为x0 满足x0 x b d modn 中国剩余定理CRT 设m1 m2 mk是两两互素的正整数 即gcd mi mj 1 i j i j 1 2 k则同余方程组 x b1 modm1 x b2 modm2 x bk modmk 模 m1 m2 mk 有唯一解 即在 m1 m2 mk 的意义下 存在唯一的x 满足 x bimod m1