数论总结（1）

阳光穿透心脏的1/2处 2022-07-15 05:52 613阅读 0赞

### 数论定理： ###

#### 1~n内的质数个数:nln(n)(实际偏小,越趋近于+∞越准确,估计复杂度是够的) ####

### 约数个数定理 ###

定义g(x),为x的约数个数  
对于一个数i，可分解成若干质数幂次的乘积，即

#### i=prime\[1\]a∗prime\[2\]b∗..... ####

#### g(i)=(a\+1)∗(b\+1)∗...... ####

### 整除的基本性质 ###

a|b b|c   =>   a|c
    a|b a|c   =>   a|bc
    a|b a|c   =>   a|ib±jc   (a|b,c的线性组合)
    a|b b|a   =>   a=±b

a=ib±c => 公因子(a,b)=公因子(b,c)

*  证明
 *  假设d为b,c的公因子,即d|b,d|c
 *  则 d | ib±c=a,即d|a
 *  由d|b得 d=公因子(a,b)=公因子(b,c)
 *  反之,如果d是a,b的公因数,也能证出d是b,c的公因数

### 互素性质 ###

#### a与b,c同时互素=>a与b∗c互素 ####

#### p为素数且p|a∗b=>p|aorp|b ####

#### a∗b|candgcd(a,c)=1=>b|c ####

#### gcd(ak,b)=1\{ k>=1\}=>gcd(a,b)=1 ####

#### a≡1(modb)=>gcd(a,b)=1 ####

### 算术基本定理 ###

*  任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积
 *  n=pr11∗pr22∗...∗prkk
 *  p1<p2<...<pk均为质数,r1,r2,...rk均为正整数

### 模运算 ###

*  (a\+b)modn=(amodn\+bmodn)modn
 *  (a∗b)modn=(amodn∗bmodn)modn
 *  abmodn=(amodn)bmodn
 *  **切记 除法运算 不能模运算！！！**

### 欧几里得算法（gcd） ###

辗转相除

int gcd(int a,int b)
    {
        If(b>a) return gcd(b, a);
        if(b==0) return a;
        else return gcd(b,a%b);
    }

辗转相减（更相减损术/Stein算法）

*  a为偶数,b为奇数 gcd(a,b)=gcd(a/2,b)
 *  a为奇数,b为偶数 gcd(a,b)=gcd(a,b/2)
 *  a为偶数,b为偶数 gcd(a,b)=2\*gcd(a/2,b/2)
 *  a为奇数,b为奇数 gcd(a,b)=gcd(b,a-b) \{a>b\}
 *  （a或b=0 返回另一个值）或（a=b返回a或b）

#### 证明gcd(a,b)=gcd(b,a-b) ####

#### a=b+(a-b)=>(a,b)=(b,a-b) \{整除性质\} ####

*  优点：
 *  加法，减法和移位运算，是最基本的运算，时间消耗最小
 *  乘法，除法，取余运算较慢

### 扩展欧几里得算法（exgcd） ###

*  求不定方程a∗x\+b∗y=1的一组解的方法
 *  由 a∗x1\+b∗y1=gcd(a,b)=gcd(b,amodb)=b∗x2\+\[a−⌊a/b⌋∗b\]∗y2=a∗y2\+b∗(x2−y2∗⌊a/b⌋)
 *  =>x1=y2
 *  =>y1=x2−y2∗(a/b)

#### \- 用途： ####

#### 1）求解不定方程； ####

#### 2）求解模线性方程（线性同余方程）； ####

#### 3）求解模的逆元； ####

#### 1)求解不定方程 ####

利用扩展欧几里得算法求解不定方程a∗x\+b∗y=n的整数解的求解全过程，步骤如下：

#### (1)先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b),得到新的不定方程a2∗x\+b2∗y=n2此时Gcd(a2,b2)=1; ####

#### (2)利用扩展欧几里德算法求出方程a2∗x\+b2∗y=1的一组整数解x0,y0,则n2∗x0,n2∗y0是方程a2∗x\+b2∗y=n2的一组整数解； ####

#### (3)根据数论中的相关定理,可得方程a2∗x\+b2∗y=n2的所有整数解为： ####

#### x=n2∗x0\+b2∗t ####

#### y=n2∗y0−a2∗t(t=0,1,2，……) ####

#### 调整得到正整数解. ####

### 最小公倍数（lcm） ###

#### lcm（a,b）=a∗b/gcd(a,b) ####

### 快速幂 ###

#### 其实就是倍增的思想 ####

#### a1,a2,a4...a2n依次求出来依次求出来 ####

#### 所以快速+幂/乘/加 都可以 ####

### abmodn ###

*  b and 1 取出二进制下最后一位
 *  b shr 1 去掉二进制下最后一位
 *  ab=a2n⋅......⋅a16⋅a8⋅a4⋅a2
 *  每次求出a2i,若二进制下该位为1，即有这位对结果的贡献，乘a2i

### 矩阵乘法求斐波那契数列 ###

\[acbd\]n

\{ F\[N−1\]=a⋅F\[N−2\]\+b⋅F\[N−1\]F\[N\]=c⋅F\[N−2\]\+d⋅F\[N−1\]

⎧⎩⎨⎪⎪⎪⎪a=0b=1c=1d=1  
\[F\[N−1\]F\[N\]\]=\[0111\]⋅\[F\[N−2\]F\[N−1\]\]

\[F\[N−1\]F\[N\]\]=\[0111\]N−1⋅\[F\[0\]F\[1\]\]

### 矩阵乘法优化递推式 ###

例如：a\[n\]=a\[n−1\]\+a\[n−2\]\+5  
⎡⎣⎢a\[N−1\]a\[N\]1⎤⎦⎥=⎡⎣⎢110100501⎤⎦⎥⋅⎡⎣⎢a\[N−2\]a\[N−1\]1⎤⎦⎥

### 线性筛 ###

O(N−−√)

#### 我们知道对于一个的他的因子的大小不超过N−−√,所以线性筛预处理,再取模判断即可 ####

O(log2n)

#### 费马小定理:当p为素数时ap≡a(modp)即ap−1≡1(modp) ####

#### 我们枚举几个a判断是否成立即可,要求选取的2<a<p,ap(modp)用快速幂处理 ####

### 欧拉函数 ###

#### 性质 ####

#### 欧拉函数phi(n)等于不超过n且和n互素的整数个数。 互素：两个数的最大公约数为1的数称为互素数。 ####

#### 1. φ(n)表示n以内与n互素(包括1)的数的个数 ####

#### 2. 欧拉定理：若a与n互质，那么有aφ(n)≡1(modn)用于求乘法逆元 ####

#### 3. 若p是一个质数，那么φ(p)=p−1，注意φ(1)=1。 ####

#### 4. 积性函数 : ####

#### 若m与n互质，那么φ(n∗m)=φ(n)∗φ(m)。 ####

#### n=pk且p为质数，那么φ(n)=pk−p(k−1)=p(k−1)∗(p−1) ####

#### 5. 当n为奇数时有φ(2∗n)=φ(n) ####

#### 6. ∑d|nφ(d)=n ####

#### 7. φ(n)=n∏p为素数且p|np−1p ####

#### 单个欧拉函数求法： ####

int euler_phi(int n)
    {
        int m=sqrt(n+0.5),ans=n;
        for(int i=2;i<=m;i++)
            if(n%i==0)
            {
                ans=ans/i*(i-1);
                while(n%i==0) n/=i;
            }
        if(n>1) ans=ans/n*(n-1);
        return ans;
    }

#### 函数表：多个欧拉函数一起求，类似筛选法计算phi(1),phi(2),……phi(n)： ####

int phi[MM]
    void phi_table(int n)
    {
        mem(phi,0); phi[1]=1;
        for(int i=2;i<=n;i++)
            if(!phi[i])
                for(int j=i;j<=n;j+=i)
                {
                    if(!phi[j]) phi[j]=j;
                    phi[j]=phi[j]/i*(i-1);
                }
    }

### 求解模方程组 ###

#### 中国剩余定理可以求解模数互质的情况,但我们用其他方式合并。 ####

#### \{ xmoda1=b1xmoda2=b2 ####

#### \{ x=a1∗x1\+b1x=a2∗y1\+b2 ####

#### 得到a1∗x1\+b1=a2∗y1\+b2 ####

#### 扩展欧几里得求出x1 ####

#### 令b=a1∗x1\+b1a=lcm(a1,a2) ####

#### 然后我们合并为xmoda=b ####

### 莫比乌斯函数 ###

#### 性质 ####

#### 对于任意正整数n有： ####

∑d|nμ(d)=\{ 10d=1d>1

#### 对于任意正整数n有: ####

### ∑d|nμ(d)d=φ(n)n ###

O(N)求解1∼n的μ(i)表

int isprime[N],mu[N],prime[N];
    int cnt;
    void Mobius(int n)
    {
        int i,j;
        //Init isprime[N],mu[N],prime[N],全局变量初始为0
        cnt=0;mu[1]=1;
        for(i=2;i<=n;i++){
            if(!isprime[i]){
                prime[cnt++]=i;
                mu[i]=-1;
            }
            for(j=0;j<cnt && i*prime[j]<=n;j++){
                isprime[i*prime[j]]=1;
                if(i%prime[j])
                    mu[i*prime[j]]=-mu[i];
                else {mu[i*prime[j]]=0;break;}
            }
        }
    }

### 求逆元 ###

逆元

> 它是一个可以取消另一给定元素运算的元素。  
> 对于正整数a和m，如果有a⋅x≡1(mod m)，那么把这个同余方程中x的最小正整数解叫做a模m的逆元。

#### 前提: ####

#### 求a(modm)意义下的逆元,要求a与m互质,否则不存在乘法逆元 ####

定理

欧拉定理(费马小定理)

#### 欧拉定理：若a与m互质，那么有aφ(m)≡1(modm) ####

#### 方法: ####

#### 1.欧拉定理 ####

根据欧拉定理 :

#### aϕ(m)a⋅aϕ(m)−1a−1≡≡≡11aϕ(m)−1(modm)(modm)(modm) ####