费马小定理和欧拉定理

ezoiHY · 2018-09-13 13:37:04 · 个人记录

费马小定理和欧拉定理

1.费马小定理

1）定义

我们现在设正整数a,m且m是素数我们就会有式子

a^{m-1}\equiv1(mod\ m)

2）证明

我们设一个完全剩余系A=\{1,2,3,...,m-1\} 又因为(a,m)=1 我们又得到另一个完全剩余系B=\{1a,2a,3a,...,(m-1)a\} 根据完全剩余系的性质我们可以轻松得到

(m-1)!\equiv(m-1)!*a^{m-1}(mod\ m)

消去就可得

a^{m-1}\equiv1(mod\ m)

2.欧拉定理

1）欧拉函数

欧拉函数记为\phi，且通常定义在正整数域上比较直接点，欧拉函数通式是长这样的

\phi(n)=n\prod^{x}_{i=1}(1-\frac{1}{p_i})

其中x为n的质因数个数，而p_i是n的第i个质因数其实欧拉函数更重要的意义是：\phi(n)表示小于等于n且与n互质的正整数的个数 由此我们可以的这么一条伪通式

\phi(n)=\sum^{n}_{i=1}[(n,i)==1]

欧拉函数是积性函数,由它的意义我们可以很容易用乘法原理证明，同时显然可以知道这不是完全积性函数若(n,m)=1，则有

\phi(nm)=\phi(n)*\phi(m)

我们可以根据定义得到如果n为素数，则\phi(n)=n-1，这个东西反向也是成立的我们可以根据这些性质来写出欧拉函数的线性筛法代码如下：

void getEuler(int x){
    eul[1]=1;
    for(int i=2;i<=x;i++){
        if(!eul[i]){
            pri[++tot]=i;
            eul[i]=i-1;
        }
        for(int j=1;j<=tot and i*pri[j]<=x;j++){
                if(!(i%pri[j])){
                    eul[i*pri[j]]=eul[i]*pri[j];
                    break;
                }
                eul[i*pri[j]]=eul[i]*(pri[j]-1);
            }
    }
}

2）定义

现在我们来引入欧拉定理，实际上欧拉定理就是费马小定理的推广在m为素数时显然就是费马小定理我们先定义两个互质的正整数a,m 我们就会有

a^{\phi(m)}\equiv1(mod \ m)

3)证明

我们令r=\phi(n) 我们先设一个有r个元素的集合P=\{p_1,p_2,p_3,...p_r\}，其中p_i是第i个与m互质的数又因为(a,m)=1，且P集合中的所有元素都与m互质，所以集合P'=\{ap_1,ap_2,ap_3,...ap_r\}的所有元素都与m互质，且属于模m的r个不同的剩余类[p_1],[p_2],..[p_r]，这里我们用同余的性质很容易就可以想到

a^r*\prod_{i=1}^{r}{p_i}\equiv\prod_{i=1}^{r}{p_i}(mod \ m)

消去可得

a^r\equiv1(mod\ m)

所以

a^{\phi(m)}\equiv1(mod\ m)

3.如何食用欧拉定理和费马小定理

1）数学问题

我们可以看这么一道题例题：13^{2017}模25的余数思路：这题我们可以求出\phi(25)然后根据同余的性质就可以解了

2）信息学

我们来看一道神奇的题

欧拉心算

给出一个正整数n(n<=10^7)，求

\sum_{i=1}^{n}\sum_{j=1}^{n}\phi({gcd(i,j)})

思路：

显然我们暴力是过不了的我们要考虑O(n)或者更高效的算法

我们肯定要推式子，所以直接拿那个题目的式子来推

其中

sum(n)=\sum_{i=1}^{n}\phi(i)

这样我们就可以推出原式为

2*\sum^n_{d=1}{(\phi(d)*sum(\lfloor \frac{n}{d} \rfloor))}-sum(n)

所以我们可以用线性筛筛出欧拉函数然后我们再求一次前缀和

代码：

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int tot,n,pri[10000001];
long long eul[10000001];

inline int rd(){
    register int x=0,y=1;register char c=getchar();
    while(c<'0' or c>'9'){
        if(c=='-')y=-1;
        c=getchar();
    }
    while(c>='0' and c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*y;
}

void getEuler(int x){
    eul[1]=1;
    for(int i=2;i<=x;i++){
        if(!eul[i]){
            pri[++tot]=i;
            eul[i]=i-1;
        }
        for(int j=1;j<=tot and i*pri[j]<=x;j++){
                if(!(i%pri[j])){
                    eul[i*pri[j]]=eul[i]*pri[j];
                    break;
                }
                eul[i*pri[j]]=eul[i]*(pri[j]-1);
            }
    }
    for(int i=2;i<=x;i++)eul[i]+=eul[i-1];
}

long long solve(int x){
    long long ret=0;int nxt;
    for(int i=1;i<=x;i=nxt+1){
        nxt=x/(x/i);
        ret+=(eul[nxt]-eul[i-1])*eul[x/i]*2-(eul[nxt]-eul[i-1]);
    }
    return ret;
}

int main(){
    n=rd();
    getEuler(10000000);
    while(n--){
        int x=rd();
        printf("%lld\n",solve(x));
    }
    return 0;
}