20130116数论.ppt

怀化学院 计算机系 2012 怀化学院ACM培训 本次课程的主要内容 数论 前言 过硬的基础就好比在武侠小说中拥有非凡的内功一样 只有将内力提升了 才能在使出华丽的招式的同时带来巨大的杀伤力 这对于程序设计来说也是一样的道理 平时做好了基础知识的积累 还有对一些常用的函数和算法进行建库 在后来的使用中就能如鱼得水 达到事半功倍的效果 我相信大象跟芦苇大家都熟悉吧 我需要你们的基础要像大象一样牢固 虽然芦苇外观看起来很华丽但是它是漂浮在水上的 很容易被风击倒 也就是说只有我们的基础打捞了那么我们就随便怎么弄 我们都能讲出个所以然来 这样大家才会信服 这样我们才能有所作为 介绍几个标准输入输出函数 1 puts 函数puts 函数用来向标准输出设备 屏幕 写字符串并换行 其调用格式为 puts s 其中s为字符串变量 字符串数组名或字符串指针 puts 函数的作用与语printf s n s 相同 例4 main chars 20 f 定义字符串数组和指针变量 strcpy s Hello TurboC2 0 字符串数组变量赋值 f Thankyou 字符串指针变量赋值 puts s puts f 说明 1 puts 函数只能输出字符串 不能输出数值或进行格式变换 2 可以将字符串直接写入puts 函数中 如 puts Hello TurboC2 0 介绍几个标准输入输出函数 2 gets 函数gets 函数用来从标准输入设备 键盘 读取字符串直到回车结束 但回车符不属于这个字符串 其调用格式为 gets s 其中s为字符串变量 字符串数组名或字符串指针 gets s 函数与scanf s 介绍几个标准输入输出函数 说明 1 gets s 函数中的变量s为一字符串 如果为单个字符 编译连接不会有错误 但运行后会出现 Nullpointerasignmemt 的错误 3 putchar 函数putchar 函数是向标准输出设备输出一个字符 其调用格式为 putchar ch 其中ch为一个字符变量或常量 putchar 函数的作用等同于printf c ch 4 getchar 函数getchar 函数也是从键盘上读入一个字符 并带回显 它与前面两个函数的区别在于 getchar 函数等待输入直到按回车才结束 回车前的所有输入字符都会逐个显示在屏幕上 但只有第一个字符作为函数的返回值 getchar 函数的调用格式为 getchar 介绍几个标准输入输出函数 5 cin getline 可以读一行有三个参数 cin getline 接受字符串的看哦下面那个m 接受个数5 结束字符 当第三个参数省略时 系统默认为 0 如果将例子中cin getline 改为cin getline m 5 a 当输入jlkjkljkl时输出jklj 输入jkaljkljkl时 输出jk以上这几种输入的方法是非常有用的 一般书上都没有进行详细讲解 希望大家能够好好掌握 代码风格你的代码命名方式是什么 注解 一般的函数内在重要地方加点注解函数内有没有需要特别注意的地方 如在里面分配内存 但要外面释放如果有 那么在函数注解中写出 一 初等数论的概念 1 整除性和约数 假设d和a是整数 d a 读作d整除a 意味着存在某个整数k 有a kd 如果d a 并且d 0 则称d是a的约数 每个整数a都可以被其平凡约数1和a整除 a的非平凡约数也称为a的因子 2 素数和合数对于某个整数a 1 如果它仅有平凡约数1和a则称p是素数 否则p是合数 可以证明素数有无限多个 筛法求素数 一 初等数论的概念 3 求素数方法1 p N 存储所有的素数 二重循环 用已经求出的不大于平方根的所有素数试除for i 2 i n i for j 0 j m2 给定一个范围 求这个范围内的素数 进行如下步骤 a 从2开始 2是第一个素数 也是第一个新素数 取出2 b 筛掉所有新素数的倍数 c 留下来的数里面第一个 最小的 是新素数 取出这个新素数 d 重复1和2直到没有数存在 一 初等数论的概念 4 除法定理 余数除法定理 对任意整数a和任意正整数n 存在唯一的整数q和r 使得a qn r 其中0 r n 值q成为除法的商 值r a modn 称为除法的余数 其平凡约数1和a整除 a的非平凡约数也称为a的因子 5 公约数与最大公约数d是a的约数并且也是b的约数 则d是a和b的公约数 两个不同时为0的整数a和b的最大公约数表示为gcd a b 一 初等数论的概念 6 gcd a b 的性质 定理 如果a b是不全为0的任意整数 则gcd a b 是a与b的线性组合 ax by x y Z 中的最小正元素 推论1 对于任意整数a b 如果d a并且d b 则d gcd a b 推论2 对于所有整数a和b以及任意非负整数n gcd an bn n gcd a b 推论3 对所有正整数n a和b 如果n ab并且gcd a n 1 则n b 7 互质数 如果两个整数a与b只有公因数1 即如果gcd a b 1 则a与b称为互质数 互素 定理 对任意整数a b和p 如果gcd a p 1且gcd b p 1 则gcd ab p 1 一 初等数论的概念 8 最大公约数gcd 最大公因子 GCD递归定理 对任意非负整数a和任意正整数b gcd a b gcd b amodb GCD算法GCD a b ifb 0thanreturnaelsereturnGCD b a b 9 二进制最大公约数算法 如果a和b都是都是偶数 那么gcd a b 2gcd a 2 b 2 如果a是奇数 b是偶数 那么gcd a b gcd a b 2 如果a和b都是奇数 那么gcd a b a b 2 b 一 初等数论的概念 10 唯一因子分解唯一质因子分解定理 合数a仅能以一种方式 写成如下的乘积形式 a p1e1p2e2 prer其中pi为素数 p1 p2 pr 且ei为正整数 课外学习 思考 将两个整数的欧几里德算法推广到求m个整数的最大公约数 算法一 扩展欧几里德算法算法二 中国剩余定理算法三 欧拉函数 二 初等数论例题讲解 例题一人见人爱A B 1739 题目描述求A B的最后三位数表示的整数 说明 A B的含义是 A的B次方 输入输入数据包含多个测试实例 每个实例占一行 由两个正整数A和B组1 A B 10000 如果A 0 B 0 则表示输入数据的结束 不做处理 对于每个测试实例 请输出A B的最后三位表示的整数 每个输出占一行 输出对于每个测试实例 请输出A B的最后三位表示的整数 每个输出占一行 样例输入23126678910000样例输出89841 二 初等数论例题讲解 例题一分析 这道题是大数吗 由于数据过大我们不能直接将a的n次方求出来 根据乘法的性质我们可以知道 a a m a m a m 故此题只要采取此种办法即可解决数据量过大的情况m 1000 解决代码如下 二 初等数论例题讲解 例题二K尾相等数问题 1023 描述一个自然数K 2 K 若存在自然数M和N M大于N 使得K M和K N均大于或等于1000 且它们的末尾三位数相等 则称M和N是一对 K尾相等数 输入输入包含若干个测试用例 每个测试用例占一行 为一个自然数K 输出对每个测试用例 用一行输出符合要求的最小M N值 样例输入2样例输出120 二 初等数论例题讲解 例题二题目分析上面的题目而言 我们必须注意到下面的要点 1 四个要点量 K M N 1000 且K M N是自然数2 K是M N的底数 M N是K的幂 3 K M和K N都必须大于10004 K M和K N末尾三位相等 5 要输出的的是M N的值6 M N7 末尾三位相等是什么意思 比如123456末尾三位是 456 而45678末尾三位则是 678 8 仔细思考后 我们可以注意到 任何数对1000求模只有1000种可能 0 999 所以我们将K Power中的Power从1 为什么不是0 因为K 0 1 1000 而我们不考虑小于1000的情况 题解第3点 到1001逐个求值 总有相等的两个数字 因为结果只有1000种可能 但是有1001次求值 哪怕前1000次所求结果都不一样 最后一次的值必然与前面1000种其中的一种相等 二 初等数论例题讲解 例题二题目分析流程 根据上面的理解和分析 解决流程大致如下 1 获得K的大小2 逐个求K Power Power 1 2 3 1001 的结果并记录下来3 若在记录的时候发现之前该值已经出现过 那么上次记录该值时的Power值和本次尝试记录时的Power值就分别是N和M了4 输出M N 二 初等数论例题讲解 例题二题目分析实现技巧 1 其实这个程序不需要什么数据结构 但是有一个技巧还是得提到一下 K Power末尾的三位数字只可能是0 999中的一种 而我们如何记录哪一种结果曾经出现过 最好的方法是使用一个一维数组 维数刚好是1000 分别记录0 999每种情况出现时Power的值 存取的时候可以利用末尾三位数本身的值作为该数组的索引来进行 相关知识 重复计数2 2 其实我们也不需要逐个求K Power的值 那样的运算效率太低了 考虑到K Power K Power 1 所以 利用这一性质 我们可以求出K 1的值 然后据此推出K 2到K 1001的结果就行了 3 当K或者Power比较大的时候它们相乘可能导致数据溢出 这就需要参考我的另一篇文章里的对大数进行求模运算的相关算法了 总之结果就是求M N R 当M N可能溢出时 应该使用 M R N R R来计算 最好采用64位整数 二 初等数论例题讲解 例题二题目源码 二 初等数论例题讲解 例题三 KittyNumber 3015 描述AKittyNumberNisapositiveintegersatisfiesthatgivenanytwopositiveintegersAandB andamongA BandN wehaveN A 2 B 1 ThenN A 2 B Now youareaskedtojudgeagivenpositivenumberisKittyNumberornot hit X YmeansXisafactorofY forexample3 9 X 2meansXmultipliesitself forexample3 2 9 X YmeansXmultipliesY forexample3 3 9 输入Thefirs