1、數論初步: 一，整除與因式分解: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,之

2、后每次對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 =

3、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

4、 <= 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 <= num; i+) if (num%isprimei =

5、 0) arr+m = isprimei; rm = 0; while (num % isprimei = 0 && num) rm+; num/= isprimei; if (num > 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

6、*=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 = 214

7、7483647:sum = m+1.sum = (p1a1)+p2a2.+pnan.1,(四省賽)題意：求x,y,滿足x+y = a,lcm(x,y) = b ,x,y.思路：因為，a<20000,b<=109.一開始想法是從1到a/2枚舉x,然后再判斷lcm是否為b.可是數據組數有105這樣會TEL。然后再想想發現，因為lcm(x,y) = b,所以x必定為b的因子，于由只要枚舉b的因子就行了。常識：1到106內平均的約數個數僅為13.97個。void dfs (int now,int q,int m,int a,int b) if (flay) return ; if (q &

8、gt; 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.)。

9、變形題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

10、),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

11、, tmp; LL xsum; for (int i = 0; i < cnt && isprimei*isprimei <= k; i+) if (k % isprimei = 0) xsum = 0; while (k % isprimei = 0) k /= isprimei; xsum +; tmp = getsum (n,isprimei); tmp /= xsum; ans = min (ans,tmp); if (k > 1) tmp = getsum (n,k); ans = min (ans,tmp); return ans;二,毆拉函數:

12、定義:對于正數n,毆拉函數是小于等于n的數中與n互質的數的個數:f (n);如果n 是素數: f(n) = n 1; f(nk) = nk nk-1;容易證明 (n) = pk - p(k-1)  證明： 少于小于pk的正整數個數為pk-1個，其中 和pk不互質的正整數有p×1,p×2,.,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,

13、 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 <= n; i+) if(n % i = 0) n /= i; ret *= i-1; while (n % i = 0) n

14、/= i; ret *= i; if (n > 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<=N,并且gcdX,N>= M.算法:由:1<=x<=N 且(x,N) >= M;得(N/M,x/M) >= 1 推出

15、: (N/q,x') = 1當1<=x'<= N/q且q >= M ;所以推出結果就是統計:sum (euler (N/q)當q|N,且q >= M 所以:只要對N進行因子分解,求出它的約數,再統計約數q大于M的euler (N/q);3,hdu 3501(2021HIT多校)求小于N的不與N互質的數的和思路：容斥原理，求反面。設：小于N與N互質的數為：a1,a2.aphi(N);對于1<= i <= phi(N),因為：gcd (N,ai) = 1 可得gcd (N,N-ai) = 1;(反證法，設gcd (N,N-ai) = k >

16、 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 <iostream>#include <cs

17、tring>#include <cmath>#include <cstdio>#include <algorithm>#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)

18、 return 0; return 1;void getprime () cnt = 2; isprime0 = 2; isprime1 = 3; for (int i = 5; i < maxn; i+) if (isok (i) isprimecnt+ = i;LL Mypro(LL a,LL b, LL c) LL ret = 0; while (b > 0) if (b & 1) if (ret += a) > c) ret -= c; if (a+=a)> c) a -= c; b >>= 1; return ret;LL Mypow (L

19、L 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 =

20、(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; retur

21、n 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 <= n;

22、i+) if (n % isprimei = 0) pim+ = isprimei; n /= isprimei; while (n % isprimei = 0) n /= isprimei; if (n > 1) pim+ = n; n = N; printf ("%lldn",(sum (n) - dfs (0,n)%mod+ mod)%mod); return 0;for (int ind = 1; ind < (1 << cnt); +ind

23、)             int token = ind;              LL tmp = 1;             &#

24、160;int t = 0;              for (int j = 0; j < cnt; +j, token >>= 1)             

25、0;                  if (token & 0x1)                          

26、;              tmp *= vtj;                      +t;          

27、;                                    if (t & 0x1)        

28、0;                       res = ( res + ( MOD - ( pow_mod(tmp, 4) * fun(n / tmp) % MOD ) ) 

29、) % MOD;                            else                  &#

30、160;             res = ( res + pow_mod(tmp, 4) * fun(n / tmp) ) % MOD;                

31、0;         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Ø

32、;性質3:a|b,a|c <=> a|xb±ycØ性質4:a|b,b|a <=> a=±bØ性質5:a=kb±c <=> 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,推出bx±cy = a(q1*x±

33、q2*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

34、-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) =

35、 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+操

36、作，那么就可以得到方程：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|盡可能小(x<0,表示砝碼和物體放在同一側)Ø先求出不定方程的一組特

37、解(x0,y0),令m=gcd(a,b),a'=a/m,b'=b/m,那么通解為x=x0+b't,y=y0-a't(a',b'>0,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 是整數，所

38、以 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&

39、gt;=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&

40、gt;=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*y

41、y>=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=bmod m.例如：5|(7-2),那么:7=2(mod5).如果：a1 = b1(mod m)且a2=b2(mod m),那么：a1±a2 = b1±b2(mod m)和a1*a2=b1*b2(mod m)成立。解同余式：ax = c (mod m).線性同余式定理：設a,c與m是整數，m&g

42、t;= 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 <iostream>2 #include <m

43、ath.h>3 #include <stdio.h>4 #include <string.h>5 #include <algorithm>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 232

44、4 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<< k;33 c = B - A;34 LL d,x,y;35 ex_gcd (a,b,d,x,y);36 if (c % d !=

45、 0)37 38 printf ("FOREVERn");39 continue;40 41 x = x*c/d;42 b = b / d;43 if (x >= 0) x = x%b;44 else x = x%b + b;45 printf ("%I64dn",x);46 47 return 0;48 Hdu3049, 2021 Multi-University Training Contest 14 - Host by ZJNU題意是求 , 你可以設：mod N =0. 將最終的結果p mod 1000003.算法流程：1，預處理，

46、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 <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#define LL _int64#define mod 1000003using namespace std;LL ff40007;void init () ff0 = 1; for (int i = 1; i < 40001; i+) ffi = ffi-1*2%mod;void ex_gcd (LL a,LL b,LL