锐客网

  1. 首页 > it技术 > >

简单数论知识梳理(省选复习)

数论

(noip数论算法汇总)
①扩展欧几里得

int ex_gcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } int g=ex_gcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; return g; }

应用及要点：
one :求形如ax+by=gcd(a,b)的一组解(x,y)（有解情况当且仅当ab互质）
要注意的是,已知一组解(x0,y0),则其他所有解都可以表示成(x0+k*b,y0-k*a)
【简单数论知识梳理(省选复习)】想像成直线就可以理解了
two:求逆元，ax≡1 mod(p) 可以转化为 ax-py=1


另：
辗转相除和辗转相减法两个定理：
辗转相减法：gcd(a,b)=gcd(a-b,b)
辗转相除法：gcd(a,b)=gcd(a%b,b)
②分解质因数
O(sqrt(n))太无脑了无视掉
O(n)预处理和O(log(a))分解:
线性筛法预处理 dy[i] 表示i的最小质因子在prime数组中的编号
分解时每次除以最小质因子即可做到log的分解质因数
代码:

void init() { for(int i=2; i<=n; i++) { if(!vis[i])prime[++cnt]=i; for(int j=1; j<=cnt; j++) { long long tmp=prime[j]*i; if(tmp>=N)break; vis[tmp]=1,dy[tmp]=j; if(tmp%prime[j]==0)break; } } } int num[N]; void work(int x) { while(x!=1) { num[dy[x]]++; x/=prime[dy[x]]; } }



③逆元：
常用的有三种,扩展欧几里得上面提到了,下面只写费马小定理和线性递推求逆元
费马小定理：a^(p-2)是a在膜p意义下的逆元，即a^(p-1)%p=1

ll qm(ll a,ll b) { ll ret=0,t=a; while(b) { if(b&1)ret=ret*t%mod; t=t*t%mod; b>>=1; }return ret; } ll inv(ll x){return qm(x,mod-2); }

线性递推逆元:inv[1]=1,inv[i]=inv[p%i]*(p-p/i)%p
让我来认真的证明一次上式.....(noip前真的是差到连这玩意都不会证.......)
设 t=p/i,k=p%i
则 p=t*i+k
即 (t*i+k)≡0(mod p)
=>-t*i≡k(mod p)
两边同时除以i*k
=> -t*inv[k]≡inv[i](mod p)
故inv[i]=-t*inv[k](mod p)
转成正数：inv[i]=(-t+p)*inv[k](mod p)
所以 inv[i]=(p-p/i)*inv[p%i](mod p)
可以愉快的线性推逆元啦23333

int inv[N]; void init() { inv[1]=1; for(int i=2; i

④欧拉函数：
线性筛求欧拉函数前面一篇博客里已经提到过，在此不提
欧拉函数的意义:
phi[n]=小于n的数中与n互质的数的个数
定义式：
phi[n]=n*(1-1/p1)*(1-1/p2)*(1-1/p3)....(1-1/pk)
这很简单就不放代码了。
应用：
one ：上一个求逆元中还有一种方法没有说到就是欧拉函数。
有欧拉定理：a^φ(n)≡ 1 mod n
two ： 按定义，求小于n且与n互质的数的个数(2333)
three：求n以内与n互质的数的和
有公式：sum(n)=phi(n)*n/2; (sum(n)为小于n的所有与n互质的数的和)


⑤一些实用的定理：
约定：
唯一分解式形为n=p1^a1*p2^a2*p3^a3*…*pk^ak
约数个数定理： n的约数个数=(a1+1)*(a2+1)*(a3+1)....(ak+1)
约数和定理：n的约数和=(p1^0+p1^1+p1^2...p1^a1)*(p2^0+p2^1+p2^2....p2^a2)...(pk^0+pk^1...pk^ak)
基础的数论知识差不多就是这些了，后面几篇博客会对几个重要的数论知识点进行详解或较多例题复习
⑥等比数列求和的分治算法：
定理：
对于Sn=a^1+a^2+...+a^n
当n==0时Sn=1; n==1时Sn=a
当n为偶数时：
Sn=S(n/2)*(a^(n/2)+1)
当n为奇数时：
Sn=S(n/2)*(a^(n/2+1)+1)+(a^(n/2)+1)

    推荐阅读


    上一篇：abdroid fragment adapter 的详细介绍

    下一篇：海*人脸识别门禁java对接的（这里没有解决方法，发泄一下）