1、数论基础浙江理工大学计算机技术研究部数论相关知识n 数论 (Number Theory)是研究整数性质的一门很古老的数学分支。其初等部分是以整数的整除性为中心，包括整除性、不定方程、同余式、连分数、素数分布及数论函数等。n 对于 ACM来说，数论方面的题目在程序的编写方面不会太复杂，但若缺少相关的知识，对于很多题目也只能一筹莫展。自然数、整数和整除n 自然数：有的情况，把 0也当作自然数n 整数 a能被 d整除，记做 d|a,意味着 a=kdn 整除有下面的性质：q 若 d|a,则 d|ka; k是整数q 若 d|a且 d|b,则 d|(ab)q 若 b|a且 a|b,则 a=b整除的特殊例子
2、 (1)n 末 1位能被 2整除，则该数能被 2整除n 末 2位能被 4整除，则该数能被 4整除n 末 3位能被 8整除，则该数能被 8整除n n 末 1位能被 5整除，则该数能被 5整除n 末 2位能被 25整除，则该数能被 25整除n 末 3位能被 125整除，则该数能被 125整除n 整除的特殊例子 (2)n 若各位数字之和能被 3整除，则该数能被 3整除n 若各位数字之和能被 9整除，则该数能被 9整除n 若偶数位数字之和与奇数位数字之和的差能被 11整除，则该数能被 11整除。 11的倍数检验法也可用下述检查 7的割尾法处理！过程唯一不同的是：倍数不是 2而是 1！ n 若一个整数的
3、个位数字截去，再从余下的数中，减去个位数的 2倍，如果差是 7的倍数，则原数能被 7整除。如果差太大或心算不易看出是否 7的倍数，就需要继续上述截尾、倍大、相减、验差的过程，直到能清楚判断为止。例如，判断 133是否 7的倍数的过程如下： 13 32 7，所以 133是 7的倍数；又例如判断 6139是否 7的倍数的过程如下： 613 92 595 ， 59 52 49，所以 6139是 7的倍数，余类推。整除的特殊例子 (3)n 若一个整数的个位数字截去，再从余下的数中，加上个位数的 4倍，如果和是 13的倍数，则原数能被 13整除。如果和太大或心算不易看出是否 13的倍数，就需要继续上述截
4、尾、倍大、相加、验差的过程，直到能清楚判断为止。n 若一个整数的个位数字截去，再从余下的数中，减去个位数的 5倍，如果差是 17的倍数，则原数能被 17整除。如果差太大或心算不易看出是否 17的倍数，就需要继续上述截尾、倍大、相减、验差的过程，直到能清楚判断为止整除的特殊例子 (4)n 若一个整数的个位数字截去，再从余下的数中，加上个位数的 2倍，如果差是 19的倍数，则原数能被 19整除。如果差太大或心算不易看出是否 19的倍数，就需要继续上述截尾、倍大、相加、验差的过程，直到能清楚判断为止。n 若一个整数的末三位与 3倍的前面的隔出数的差能被 17整除，则这个数能被 17整除。 n 若一个
5、整数的末三位与 7倍的前面的隔出数的差能被 19整除，则这个数能被 19整除。n 若一个整数的末四位与前面 5倍的隔出数的差能被 23(或 29)整除，则这个数能被 23整除最大公约数和最小公倍数n 如果 d是 a的约数也是 b的约数则 d 是 a与 b的公约数，最大公约数记做 gcd(a,b)。n 最大公约数的性质：q gcd(a,ka)=|a|q 若 d|a且 d|b,则 d|gcd(a,b)q n非负 ,gcd(an,bn)=ngcd(a,b)q a,b,d正整数，若 d|ab且 gcd(a,d)=1,则 d|bq 若 q和 r是 a除以 b的商和余数，即 a=b*q+r,则gcd(a,b)=gcd(b,r)n 最小公倍数 lcm(a,b)=a*b/gcd(a,b)基本算法描述 (1)n 辗转相除法求最大公约数int gcd(int a, int b)if(b=0) return a;else return gcd(b, a % b);基本算法描述 (2)n 利用最大公约数求最小公倍数int lcd(int a, int b)if(a*b=0) return 0;else return a*b/gcd(a, b);
