数论基础(不是

一个集训的初中生啊,学大佬的数论。。。

整除与带余除法

1、已知: 7^82 + 8161能被57整除,求证:783 +81^63也能被57整除。
嗯,
证明:7^83 + 81^63 = 7 ( 7^82 + 81^61 )-7 × 8^161 + 8^163
= 7 ( 7^82 + 8^161 ) + 8^161 × 57
∵7^82 + 8^161和57都能被57整除

这其实还好。

最大公约数与最小公倍数

一看题目觉得简单???
“You are right wrong”;
数论基础(不是
`
数论基础(不是
数论基础(不是
数论基础(不是

定理
数论基础(不是
说实话,我听到这时已经兴奋崩溃了;

问题一:给定a,b,计算gcd(a,b)

方法1:枚举法
从min(a,b)到1枚举x,并判断x是否能同时整除a和b,如果可以则输出x退出循环。时间复杂度为O(min(a,b))。
方法2:分解质因子
对a,b分别分解质因子,a=p1x1p2x2…pnxn,b=p1y1p2y2…pnyn,其中xi,yi>=0且不会同时为0(1<=i<=n),则gcd(a,b)=p1min(x1,y1)p2min(x2,y2)…pnmin(xn,yn)。

(分解质因数求最大公约数)代码如下:
数论基础(不是

方法3:欧几里得算法 定理:gcd(a,b)=gcd(b,a mod b)

证明:
设gcd(a,b)=p,则有a=a’*p,b=b’*p,gcd(a’,b’)=1
a mod b=a-[a/b]b=p(a’-[a/b]*b’)
gcd(b,a mod b)=gcd(b’p,p(a’-[a/b]b’))=pgcd(b’,a’-[a/b]*b’)
证明gcd(b’,a’-[a/b]*b’)=1,
反证法,如果gcd(b’,a’-[a/b]*b’)=t(t>1)
设b’=b’’*t,a’-[a/b]*b’=c’*t,则有a’=[a/b]*b’’*t+c’t=t([a/b]*b’’+c’)
显然t|b’,t|a’,与gcd(a’,b’)=1相矛盾
所以gcd(b,a mod b)=p=gcd(a,b)

代码如下:

数论基础(不是
方法4:二进制法
①a<b时,gcd(a,b)=gcd(b,a)
②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/2)
⑥a,b同为奇数时,gcd(a,b)=gcd(a-b,b)
数论基础(不是

问题二:计算n个整数a1,a2,…,an的最小公倍数

分析:两个数a1,a2的最小公倍数lcm(a1,a2)=a1*a2/gcd(a1,a2)
lcm(a1,a2,a3)=lcm(lcm(a1,a2),a3),以此类推,可以先求a1,a2的最小公倍数b1,再求b1与a3的最小公倍数b2,再求b2与a4的最小公倍数b3…
数论基础(不是

算术唯一分解定理

算术基本定理:任一大于1的整数n 能表示成质数的乘积,且其分解的结果是唯一的[不考虑次序].
数论基础(不是数论基础(不是
数论基础(不是

素数—埃氏筛法

数论基础(不是
埃氏筛法中,以n=50为例,30这个数被筛了3次,分别是215(p=2),310(p=3),510(p=5),这里降低了程序效率,我们可以让每个合数只被最小的素因子筛除,这样每个数最多只被筛一次。具体如下:
枚举2~n中的每一个数i:
(1)如果i是素数则保存到素数表中
(2)利用i和素数表中的素数prime[j]去筛除i
prime[j],为了确保iprime[j]只被素数 prime[j]筛除过这一次,我们要确保prime[j]是iprime[j]中最小的素因子,即i中不能有比prime[j]还要小的素因子,由于我们是从小到大扫描素数表中的素数prime[j]的,假设i的最小素因子是素数表中的prime[k],那很显然:
①当j<=k时,prime[j]*i都是可以筛除的,因为prime[j]是prime[j]*i的最小素因子;
②当j>k时,由于prime[k]|i, ,prime[k]<prime[j]
prime[j]*i不应该在此处筛除,而是会在i循环执行到 时,与素数表中
的prime[j]相乘才筛除.因此只需在i % prime[j]==0时结束j循环.
显然这样,每个数只会被筛一次,时间复杂度为O(n)

就这样吧,真不行了。
成绩也出来了 语文不会数学崩溃英语颓废……
PS:陈真yyds

上一篇:排位赛(五)| B题


下一篇:NYOJ 520 解题报告