ACM中数论基础知识的运用.doc

数论初步: 一，整除与因式分解:1,算术基本定理: n =a1r1*a2r2*a3r32,求素数:(试除法,筛选法):素数测试费马小定理:若p为素数,则对于任意小于p的正整数a,有a(p-1)1(mod p)证明:用欧拉定理直接得出二次探测定理:若p为素数,a21(mod p)小于p的正整数解只有1和p-1满足费马小定理和二次探测定理的数可以确定是素数Miller-Rabin算法算法步骤:判定n是否为素数令n-1=m*2j,m为奇数随机在2到(n-1)之间取一个整数b令v=bm,之后每次对v平方,当v=1时,若上一次的v既不是1也不是(n-1),由二次探测定理,n不是素数,退出;不断循环直到计算出b(n-1)v=1,满足费马小定理,通过测试;否则n一定不是素数选取几个不同的b多次测试Miller-Rabin只能算一种测试,因为通过测试的数不一定是素数,非素数通过测试的概率是1/4虽然一次测试的结果不一定令人满意,但五六次随机测试基本可以保证正确率超过99.9%For (int i = 2; i n ;i+) For (int j = 2,flay = 1; j sqrt (n); j+)If (I % j = 0)Printf (“i不是素数”);flay = 0;Printf (“I 是素数”); 3 ,int m = sqrt (n+0.5);int c = 0;memset (vis,0,sizeof (vis);for (int i = 2; i = m; i+)if (!visi) primec+ = i;for (int j = i*i; j = n; j+= i) visj = 1;4,int isprimeN;int cnt;int isok (int x) for(int i = 0; i cnt & isprimei * isprimei = x; i+) if (x % isprimei = 0) return 0; return 1;void getprime () isprime0 = 2; isprime1 = 3; cnt = 2; for (int i = 5; i maxn; i+) if (isok (i) isprimecnt+ = i; 5,因式分解:int Factor (int num) int m = 0; for (int i = 0; i cnt & isprimei*isprimei 1) arr+m = num; rm = 1; return m;6,求约数:void dfs (int now,int q,int m,int a,int b) if (flay) return ; if (q a) return ; if (now = m+1) q 就是约数. return ; for (int i = 0,t = 1;i = rnow;i+,t*=arrnow) dfs (now+1,q*t,m,a,b); 例题分析:Fzu上的题:()求一个数的真因子个数（不包括本身）。n = p1a1*p2a2.pnan.那么真因子的个数就为：(a1+1)*(a2+1).(an+1)-1;求n的所有真因子的和。由n = p1a1*p2a2.prar.再由生成函数得(1+p1+p12.+p1a1)*(1+p2+p22.+p2a2).(1+pr+pr2.prar).求最小公倍数为的至少两个数的最小和。m = p1a1*p2a2.pnan.当m = 1时：sum = 2当m为素数时或m =pn时：sum = m+1当m = 2147483647:sum = m+1.sum = (p1a1)+p2a2.+pnan.1,(四省赛)题意：求x,y,满足x+y = a,lcm(x,y) = b ,x,y.思路：因为，a20000,b a) return ; if (now = m+1) int x = q; int y = a - x; if (lcm (x,y) = b) flay = true; if (x y) swap (x,y); printf (%d %dn,x,y); return ; for (int i = 0,t = 1;i = rnow;i+,t*=arrnow) dfs (now+1,q*t,m,a,b); 变形题1：求x,y,满足x+y =a,gcd(x,y) = b,x,y;这可以看出b为x,y,的因子，要构造x,y,只要枚举b*k(k在1.)。变形题2: 已知最大公约数gcd (x,y) = a,lcm (x,y) = b,求有多少个满足条件的?void dfs (int now,int q,int m) if (now = m+1) / if (q%x = 0) /*注释的方法会超时*/ arrp+ = q; /*设p = a*x, q = b*x ,则由gcd (p,q) = x，得 gcd (a,b) = 1 得y = a*b*x ,x*y = a*b*x*x,dfs枚举到的一个q后，q 定等于b*x, 于是将x*y/q之得到的p,判断gcd (p,q) ?= x */ int t = x*y/q; / x = gcd (p,q),y = lcm (p,q); p*q = gcd(p,q)*lcm (p,q) ; p = x*y/q; if (gcd (t,q) = x) c+; return ; for (int i = 0, t= 1; i = rnow; i+,t *= anow) dfs (now+1,q*t,m); 2,求最大的i使得n!%ki = 0; (想想:N!如何分解.)LL getsum (LL n,LL x) LL ret = 0; while (n) ret += n/x; n /= x; return ret;LL solve (LL n,LL k) LL ans = (LL)inf, tmp; LL xsum; for (int i = 0; i cnt & isprimei*isprimei 1) tmp = getsum (n,k); ans = min (ans,tmp); return ans;二,殴拉函数: 定义:对于正数n,殴拉函数是小于等于n的数中与n互质的数的个数:f (n);如果n 是素数: f(n) = n 1; f(nk) = nk nk-1;容易证明 (n) = pk - p(k-1)证明： 已知少于小于pk的正整数个数为pk-1个，其中和pk不互质的正整数有p1,p2,.,p(p(k-1)-1)共计p(k-1)-1个所以(n) = pk -1 - (p(k-1)-1) = pk - p(k-1)如果:gcd (n,m) = 1 那么:f(n*m) = f(n)*f(m);Euler定理 若gcd(a, n)=1则a(n)1 (mod n) 意义：当b很大时abab mod (n)(mod n)，让指数一直比较小所以当: n = p1a1*p2a2. F(n) = (p1a1 p1a1-1)*(p2a2 p2a2-1).= (p1-1)*(p2-1)*.(p1(a1-1)*p2(a2-1).);F(n) = n*(1-1/p1)*(1-1/p2).int elua (int n) int ret = 1; for (int i = 2; i * i 1 ) ret *= n-1; return ret;例题分析1:pku 2478, 求出分数a/b ，其中数1= a b = n并且gcd (a,b) = 1这样的分数有多少个,思路: (就是求小于n的把有整数a，并且sum (gcd (a,n) = 1(1= a n)的个数。)2,hdu 2588 : 有多少个正整数X满足： 1=X= M.算法:由:1=x= M;得(N/M,x/M) = 1 推出: (N/q,x) = 1当1=x= M ;所以推出结果就是统计:sum (euler (N/q)当q|N,且q = M 所以:只要对N进行因子分解,求出它的约数,再统计约数q大于M的euler (N/q);3,hdu 3501(2010HIT多校)求小于N的不与N互质的数的和思路：容斥原理，求反面。设：小于N与N互质的数为：a1,a2.aphi(N);对于1= i 1, = k|N 且k|(N-ai), = k|ai k|gcd (N,ai) 这与gcd (N,ai) = 1 矛盾)，所以得s = a1 + a2+aphi(N) S = N-a1 + N-a2 .+ N aphi(N) = s = N*phi(N)/2;变形题：求小于N的所有数与N的最大公约数之和。思路：设K = gcd (i,n) (1= i= n) 那么最大公约数为K的个数是phi(n/K),和就是K*phi(n/K).4,去年的大连赛区现场题：zju 3547.#include #include #include #include #include #define LL long long#define mod 1000000007#define maxn 10000using namespace std;int pi1000,m;int isprime1300,cnt;int isok (int x) for (int i = 0; i cnt & isprimei*isprimei = x; i+) if (x % isprimei = 0) return 0; return 1;void getprime () cnt = 2; isprime0 = 2; isprime1 = 3; for (int i = 5; i 0) if (b & 1) if (ret += a) c) ret -= c; if (a+=a) c) a -= c; b = 1; return ret;LL Mypow (LL a,int b,LL c) LL ret = 1; while (b 0) if (b & 1) ret = Mypro (ret,a,c); a = Mypro (a,a,c); b = 1; return ret;LL n_30;LL sum (int n) LL ret ; ret = Mypow (n,5,mod)*6%mod; ret = (ret + 15*Mypow (n,4,mod)%mod)%mod; ret = (ret + 10*Mypow (n,3,mod)%mod)%mod; ret = (ret - n)%mod; ret = (ret + mod)%mod; ret = Mypro (n_30,ret,mod); return ret;LL dfs (int x,int n) LL ret = 0; LL temp; for (int i = x; i m; i+) temp = pii; ret = (ret + (sum (n/temp)*(temp*temp%mod*temp%mod*temp%mod)%mod)%mod; ret = (ret - (dfs (i+1,n/temp)*(temp*temp%mod*temp%mod*temp%mod)%mod)%mod+mod)%mod; return ret % mod;int main () getprime (); int cs; int n; scanf (%d,&cs); n_30 = Mypow (30,mod-2,mod); while (cs-) scanf (%d,&n); if (isok (n) printf (%lldn,sum (n-1); continue; LL N = n; m = 0; for (int i = 0; i cnt & isprimei * isprimei 1) pim+ = n; n = N; printf (%lldn,(sum (n) - dfs (0,n)%mod+ mod)%mod); return 0;for(intind=1;ind(1cnt);+ind)inttoken=ind;LLtmp=1;intt=0;for(intj=0;j=1)if(token&0x1)tmp*=vtj;+t;if(t&0x1)res=(res+(MOD-(pow_mod(tmp,4)*fun(n/tmp)%MOD)%MOD;elseres=(res+pow_mod(tmp,4)*fun(n/tmp)%MOD;Euler定理 若gcd(a, n)=1则a(n)1 (mod n) 意义：当b很大时abab mod (n)(mod n)，让指数一直比较小Ax mod c = (A(x mod phi (c) + phi (c) mod c;费马小定理：设p是素数，a 是任意整数且a!=0(mod p),则有：ap-1 = 1 (mod p).三，线性方程扩展殴几里德。整除的性质性质1:a|b,b|c = a|c性质2:a|b = a|bc性质3:a|b,a|c a|xbyc性质4:a|b,b|a a=b性质5:a=kbc a,b的公因数与b,c的公因数完全相同(利用性质3)证明：性质1： 由 a|b,b|c 得：b = a*q1,c = b*q1 = c = a*q1*q2，命题得证。性质2：由a|b得：b = a*q,两边同乘以c,就得b*c = a*q*c， 命题得证。性质3：必要性：由a|b,a|c，得：b = a*q1,c = a*q2,推出bxcy = a(q1*xq2*y).取x = 1,y= 0及x = 0,y = 1,就推出充分性了，命题得证。 性质4：必要性：由a|b,b|a得b = a*q1,a = b*q2,推出a = a*q1*q2,因为a0所以q1*q2 = 1,q1 = 1, 充分性显而易见，命题得证。性质5：由性质3可得：a是b与c的公约数，同时，a又是b的约数，所以，a与b 的公约数为a等于b与c的公约数欧几里德算法(辗转相除法,短除法)原理:若ar(mod b),则gcd(a,b)=gcd(b,r)(利用性质5证明)a = q1* b + r1b = q2*r1 + r2r1 = q3*r2+r3.rn-1 = qn-1*rn-2+rn-1rn-2 = qn*rn-1+rnrn-1 = qn+1*rn + 0;二元一次不定方程形中：a*x + b*y = c.求a*x + b*y = gcd (x,y), 的一组解：（x0,y0）;void ex_gcd (LL a,LL b,LL &d,LL &x,LL &y) if (b = 0) d = a; x = 1,y = 0; else ex_gcd (b,a%b,d,y,x); y = y - x*(a/b); 那如果要求:a*x + b*y = c的一组解(x1,y1).由整除的性3可知：当c % gcd (a,b) = 0 时，方程才有解。(x0*c/g,y0*c/g); g = gcd (a,b);通解：(x1+k*b/g,y1-k*a/g);X1*a+y1*b = c = x2*a+y2*b; = (x1-x2)*a = (y2-y1)*b(x1-x2)*a1 = (y2-y1)*b1 其中：a1 = a/g,b1 = b/g;可得gcd (a1,b1) = 1,那么(x1-x2) = b1*k,(y2-y1) = a1*k;例题分析：Joj 去年的省赛题：求最少的步数操作：使得给定的Y，变成0，Y有四种操作：Y+a,Y-a,Y+b,Y-b.;算法过程：设进行了x次的a+操作，进行了y次的b+操作，那么就可以得到方程：a*x + b*y = Y;这就转换成了用殴几里德来解这个方程。得到了它的一个解(x0,y0)。通解：x = x0 +k*b/g ,y = y0 k*a/g;POJ2142题目大意: 现有质量为a和b的砝码,数量不限要求在天平上称出质量为d的物品,天平左右均可放砝码求一种可行方案,要求:放置砝码数量尽可能少;数量相同时,总质量尽可能少算法思路:问题转化:求ax+by=d的一组整数解(x,y),要求|x|+|y|尽可能小,若相等,则a|x|+b|y|尽可能小(x0,t为整数)要求输出（|x| + |y|）值最小的一组。即 （| x | + | y |）= | x0 + b / g * t | + | y0 - a / g * t | = f(t)， 简单分析，可以知道， | x0 + b / g * t | 永远递增且大于零。f(t) 只有在 | y0 - a / g * t | = 0的时候 才能取得最小值。又因为 t 是整数，所以 t 应该取 (y0 * g / a) 左右的整数值。有了这个结论,我们只需尝试至多两个解即可Zoj 3593:从A到B点，每次只能走：a或b或a+b,问最少的步数。由题意不难列出方程：x*a+y*b = B-A;解出一组解（x0,y0）.ll get_step(ll x,ll y,ll addx,ll addy) ll r,k,kx,ky,xx,yy; k=(y-x)/(addx+addy); xx=x+k*addx; yy=y-k*addy; if(xx*yy=0)r=max(abs(xx),abs(yy); else r=abs(xx)+abs(yy); xx=x+(k+1)*addx; yy=y-(k+1)*addy; if(xx*yy=0)r=min(r,max(abs(xx),abs(yy); else r=min(r,abs(xx)+abs(yy); xx=x+(k-1)*addx; yy=y-(k-1)*addy; if(xx*yy=0)r=min(r,max(abs(xx),abs(yy); else r=min(r,abs(xx)+abs(yy); kx=x/addx; ky=y/addy; xx=x-kx*addx;yy=y+kx*addy; if(xx*yy=0)r=min(r,max(abs(xx),abs(yy); else r=min(r,abs(xx)+abs(yy); xx=x+ky*addx;yy=y-ky*addy; if(xx*yy=0)r=min(r,max(abs(xx),abs(yy); else r=min(r,abs(xx)+abs(yy); return r;线性同余方程：同余的定义：如果m整除a-b,我们就说a与b 模m同余，并记之为：a=b（mod m）.例如：5|(7-2),则:7=2(mod5).如果：a1 = b1(mod m)且a2=b2(mod m),则：a1a2 = b1b2(mod m)和a1*a2=b1*b2(mod m)成立。解同余式：ax = c (mod m).线性同余式定理：设a,c与m是整数，m= 1,且设g = gcd (a,m).(a).如果c % g != 0,则同余式ax = c (mod m)没有解。(b).如是c % g = 0，则同余式ax = c(mod m)恰好有g 个不同的解。要求这些解，首先求线性方程au+mv = g的一个解（u0,v0）.则x0 = cu0/g是ax = c (mod m)的解，该方程的完全解集由：x = x0+k*m/g(mod m),k = 0,1,2g-1. 例题分析：Pku 2115题意：给一个初始值，求+xC = B(mod2k).的最小的。1 #include 2 #include 3 #include 4 #include 5 #include 67 using namespace std;8 #define LL long long910 void ex_gcd (LL a,LL b,LL &d,LL &x,LL &y)11 12 if (b = 0)13 14 d = a;15 x = 1,y = 0;16 17 else18 19 ex_gcd (b,a%b,d,y,x);20 y = y - x*(a/b);21 22 2324 int main ()25 26 LL a,b,c;27 LL A,B,C,k;28 while (scanf (%I64d %I64d %I64d %I64d,&A,&B,&C,&k) != EOF)29 30 if (A = 0 & B = 0 & C = 0 & k = 0) break;31 a = C;32 b = (LL) 1= 0) x = x%b;44 else x = x%b + b;45 printf (%I64dn,x);46 47 return 0;48 Hdu3049, 2009 Multi-University Training Contest 14 - Host by ZJNU题意是求, 你可以设：mod N =0. 将最终的结果p mod 1000003.算法流程：1，预处理，2i mod 1000003的数组。2，计算出x = (sum (2nk)mod 1000003 /nk为输入的数。3，可得方程：(sum (2nk) = x + 1000003P.4，由能整除，得：x + 1000003y = 0 (mod N).5,将得到的y代入到：x+1000003y/N mod 1000003.#include #include #include #include #include #define LL _int64#define mod 100000