interestingLSY 的博客

interestingLSY 的博客

数论部分知识积累::代数

posted on 2018-02-06 23:23:44 | under 未分类 |

数论部分知识积累::代数

重要信息:本文中的定义基本上都是我自己编的,差不多就行。如果您是那种迂腐麻木只知道背定义的人,这篇文章可能不太适合您,出门左转百度百科,谢谢。



欧拉函数

性质

以下默认 $\ {\color{Blue}{p\ is\ a\ prime}}$

$\varphi(p)=p-1$

$\varphi(mn)=\varphi(m) \times \varphi(n)\qquad gcd(m,n)=1$

如果 $\ i \mod p = 0\ $ ,那么 $\ \varphi(i \times p)=p \times \varphi(i)$

如果 $\ i \mod p \ne 0\ $ ,那么 $\ \varphi(i \times p)=(p-1) \times \varphi(i)$

板子

int n;
int phi[MAXN];
void Getphi(){
    For(i,n)
        phi[i] = i;
    Forx(i,2,n){
        if( phi[i] == i ){
            // i is a prime now
            Forstep(j,i,n,i)
                phi[j] = phi[j]/i*(i-1);
        }
    }
}


同余

$Gcd$ ( $GunChuangDan$ )

描述

$gcd(a,b)$ 表示 $a,b$ 的最大公约数

板子

int Gcd( int a , int b ){
    if(a<b) swap(a,b);
    if(!b){
        return a;
    }
    return Gcd(b,a%b);
}

扩欧(扩展欧几里德, $Exgcd$ )

描述

整数对 $x,y$ ,使得 $gcd(a,b)\ =\ ax + by$ 。

板子

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

不定方程

一篇好文

定义

看着像 $ ax+by \ = \ c$ 的式子,就是不定方程

性质

$ ax + by = c\ $ 有正整数解的条件为 $c\ mod\ gcd(a,b) = 0$

若 $x,y$ 是方程解,那么 $x+n \cdot b\ ,y-n \cdot a\ (\ n \in Z\ )$ 也是方程解

贝祖定理(裴蜀定理)

若a,b是整数,且 $gcd(a,b)\ =\ d$ ,那么对于任意的整数 $x,y$ , $ ax+by \ = \ c$ 中的 $m$ 一定是 $d$ 的倍数。

同余式(同余方程)

定义

形如 $ a \equiv b \ \color{Blue}{(mod \ c)}$ 的式子,应该就是同余式(逃

性质

$ a \equiv b + c \ {\color{Blue}{(mod \ d)}}\quad \Leftrightarrow \quad a-b \equiv c\ {\color{Blue}{(mod \ d)}}$



整除性

以下默认 $\color{blue}{p,q\ are\ primes}$

若 $p,q$ 均为质数,则 $p^a$ 与 $q^b$ 互质