7-24学习笔记

常规
1

7-24 简单 数论

真的是太简单了

组员；林育辰，郑荣，许文博，刘天顺

欧拉函数

性质：

  1. \varphi(x * y) = \varphi(x) * \varphi(y) 即函数满足积性
  2. n= \sum\varphi(n的因子)
  3. \varphi(p^k)=p^k\frac{k-1}{p},p\in{质数}

由性质1和3可推：

我们将n进行质因数分解，则有 n = {p_1}^{q_1}\times{p_2}^{q_2}\times...\times{p_k}^{q_k}($p_1,p_2…p_k$均为质数）

显然 \varphi(n)=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times...\times(1-\frac{1}{p_k})

我们就有了单点求$\varphi(n)$的方法。

单点求欧拉函数

int phi(int n){
	int ans = n, m = sqrt(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 >= 2)
  		ans = ans /  n * (n - 1);
    return ans;
}

####线性求欧拉函数

void phi(){
    phi[1] = 1;
    for(int i = 2 ; i <= 1000007 ; i ++){
        if(!vis[i]){
            p[++ cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1 ; p[j] && i * p[j] <= 1000007 ; j ++)
        {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0){
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            else 
            	phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
}

欧拉定理

若 \gcd(a,n)=1,则 a^{\varphi(n)}\equiv1(mod\ n)

欧拉定理求逆元

##裴蜀定理

若 a,b 为整数, \gcd(a,b)=d

则 x,y\in Z,ax+by 为$d$的倍数

一定存在 x,y \in Z, 使 ax+by=d

推出 ax+by+cz=n\times\gcd(a,b,c),\ (a,b,c,x,y,z,n\in Z)

exgcd

int x,y;
void exgcd(int a,int b){
    if(b==0){
        x=1;y=0;
        continue;
    }
    exgcd(b,a%b);
    int tmp=x;
    x=y;
    y=tmp-(a/b)*y;
}

\uparrow 此处求出的 x_0,y_0 为一组特解;

通解为

\begin{cases}x=x_0+\frac{b}{\gcd(a,b)}\times t\\y=y_0-\frac{a}{\gcd(a,b)}\times t\end{cases} \ t \in N

中国剩余定理

一元线性同余方程( $m_1,m_2…m_n$互质)

\begin{cases} x\equiv a_1\ (mod \ m_1)\\ x\equiv a_2\ (mod \ m_2)\\ x\equiv a_3\ (mod \ m_3)\\ ...\\ x\equiv a_n\ (mod \ m_n)\\ \end{cases}

通过一系列的证明，显然得出其解法

设 M=m_1 \times m_2 \times m_3 \times ...\times m_n=\prod_{i=1}^{n} m_i

再设 M_i=\frac{M}{m_i}

设 t_i 满足线性同余方程 M_it_i\equiv1(mod\ m_i) 的最小正整数解( i=1,2...n)

于是可以构造得, x 的一个解为: x=\sum_{i=1}^{n}a_i M_i t_i \mod M

x 的通解为: x=kM+\sum_{i=1}^{n} a_i M_i t_i , k\in Z

其他

{\Large\text{}\sigma(n):}

定义 \sigma(i) 为 i 的因子个数(积性函数).

\sigma(n) 求法

  • 因式分解:n=p_1^{q_1}\times p_2^{q_2}\times...\times p_k^{q_k}

  • \sigma(n)=(q_1+1)(q_2+1)...(q_k+1)

1 个赞