acm中数论基础知识的运用

《acm中数论基础知识的运用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数论初步:一，整除与因式分解:1,算术基本定理:n=a1^r1*a2^r2*a3^r3……2,求素数:(试除法,筛选法):素数测试Ø费马小定理:若p为素数,则对于任意小于p的正整数a,有a(p-1)≡1(modp)Ø证明:用欧拉定理直接得出Ø二次探测定理:若p为素数,a2≡1(modp)小于p的正整数解只有1和p-1Ø满足费马小定理和二次探测定理的数可以确定是素数Miller-Rabin算法Ø算法步骤:Ø判定n是否为素数Ø令n-1=m*2j,m为奇数Ø随机在2到(n-1)之间取一个整数bØ令v=bm,之后每次对v平方,当v=1时,若上一次的v既不是1也不是(n-

2、1),由二次探测定理,n不是素数,退出;不断循环直到计算出b(n-1)Øv=1,满足费马小定理,通过测试;否则n一定不是素数Ø选取几个不同的b多次测试Miller-Rabin只能算一种测试,因为通过测试的数不一定是素数,非素数通过测试的概率是1/4Ø虽然一次测试的结果不一定令人满意,但五六次随机测试基本可以保证正确率超过99.9%For(inti=2;i

3、.5);intc=0;memset(vis,0,sizeof(vis));for(inti=2;i<=m;i++)if(!vis[i]){17prime[c++]=i;for(intj=i*i;j<=n;j+=i)vis[j]=1;}4,intisprime[N];intcnt;intisok(intx){for(inti=0;i

4、for(inti=5;i1){arr[++m]=num;r[m]=1;17}returnm;}6,求约

5、数:voiddfs(intnow,intq,intm,inta,intb){if(flay)return;if(q>a)return;if(now==m+1){q就是约数…..return;}for(inti=0,t=1;i<=r[now];i++,t*=arr[now]){dfs(now+1,q*t,m,a,b);}}例题分析:Fzu上的题:(www.acm.fzu.edu.cn)求一个数的真因子个数（不包括本身）。n=p1^a1*p2^a2...pn^an.那么真因子的个数就为：(a1+1)*(a2+1)...(an+1)-1;求n的所有真因子的和。由n=p

6、1^a1*p2^a2...pr^ar.再由生成函数得(1+p1+p1^2...+p1^a1)*(1+p2+p2^2...+p2^a2)...(1+pr+pr^2...pr^ar).求最小公倍数为Ｍ的至少两个数的最小和。m=p1^a1*p2^a2...pn^an.当m=1时：sum=2当m为素数时或m=p^n时：sum=m+1当m=2147483647:sum=m+1.sum=(p1^a1)+p2^a2...+pn^an.1,(四省赛)题意：求x,y,满足x+y=a,lcm(x,y)=b,x,y.思路：因为，a<20000,b<=10^9.一开始想法是从1到a/2

7、枚举x,然后再判断lcm是否为b.可是数据组数有10^5这样会TEL。然后再想想发现，因为lcm(x,y)=b,所以x必定为b的因子，于由只要枚举b的因子就行了。常识：1到10^6内平均的约数个数仅为13.97个。voiddfs(intnow,intq,intm,inta,intb){if(flay)return;17if(q>a)return;if(now==m+1){intx=q;inty=a-x;if(lcm(x,y)==b){flay=true;if(x>y)swap(x,y);printf("%d%d",x,y);}return;}for(inti

8、=0,t=1;i<=r[