威尔逊定理/线性筛/欧几里得算法/扩欧/快速幂/筛法欧拉/欧拉定理/费马小定理/卢卡斯定理

从去年还在竞赛的时候2/12的原博客里搬运来的
不得不说之前取名真的很艺术qwq

今天开始上的数论课，让头发以肉眼可见的速度掉落emmm
没关系我头发多我不怕啦啦啦QwQ

其中最令人头疼的就是那些人名定理了，看到它们，总是在想：

我是谁

我从哪里来

我要做什么

咳咳，不是，是下面——

  • 这是什么

  • 怎么证明

  • 代码实现

  • 有什么用

其中怎么证明过于复杂了，一点也没听懂。数竞的事情关我们信竞什么事……

所以这篇博客将整理1/3/4的问题，理清楚欧拉费马欧几里得威尔逊等等名人定理之间的关系！【当然没有人名的定理也整呐！】

参考资料

数论问题算法模板 By yxc

预备知识

摘自百度百科

整除

若整数b除以非零整数a，商为整数，且余数为零， 我们就说b能被a整除（或说a能整除b）

e.g. 6÷2=3 （即6%2=3）

b为被除数，a为除数，即a|b（“|”是整除符号），a叫做b的约数（或因数），b叫做a的倍数。

约数

又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。一个整数的约数是有限的。同时，它可以在特定情况下成为公约数。

同余

给定一个正整数m，如果两个整数a和b满足a-b能够被m整除， 即**（a-b)/m得到一个整数**，那么就称整数a与b对模m同余，记作a≡b(mod m)

e.g. 26≡2(mod 12) 即26%(k*12)=2 (k∈Z)

质数

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

互质

公约数只有1的两个整数

e.g. 8,10的最大公因数是2，不是1，因此不是整数互质

算法定理

威尔逊定理 Wilson

What

p是质数，等价于 (p-1)! ≡ -1 (mod p)，即**(p-1)!%p=-1**

Code

bool Wilson(int x){
//fun函数为阶乘，略
	return (fun(n-1)+1)%n==0
}

Use

判定质数

线性筛/欧拉筛法 get_primes

在介绍线性筛之前，还有一种筛素数的方法——埃拉托斯特尼筛法

具体请绕步洛谷P3383线性筛第一篇题解

What

任何一个合数都可以表示成一个质数和一个数的乘积。总之就是拿最小因数来筛质数，来达到每个数只筛一遍，时间复杂度为O(n)

Code

int N;//范围为1~N 
int primes[10000005],cnt;//primes为素数表，cnt为素数个数 
bool st[10000005];//是否被筛过
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i])	primes[cnt++]=i;//如果没被筛过，那么就是质数，加入素数表
		for(int j=0;j<cnt&&i*primes[j]<=n;j++){//被筛的数没超出范围
			st[primes[j]*i]=true;//被筛
		}
	}
}

Use

用来筛素数，一般用于预处理。但是，
只有msqrtn比n大的时候才用线性筛，否则速度是不如暴力的（m为要筛的个数，n为范围）

欧几里得算法/辗转相除法 Euclid 1.0

What/Use

用来求最大公约数

Code

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

扩展欧几里得算法 Euclid 2.0

What/Use

预备定理：裴蜀定理

若a，b是整数，且**(a,b)=d**,【a和b的最大公因数是d】那么对于任意的整数x，y，ax+by都一定是d的倍数，特别地，一定存在整数x，y，使ax+by=d成立

扩展欧几里得算法可以在 O(logn) 的时间复杂度内求出系数 x,y

Code

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

快速幂

What

用分解的方法来求幂

e.g.先求21,22,24,28……∴21024=22*22*22……

Code

typedef long long LL;
int qmi(int a,int k,int p){
    int res=1%p;
    while(k){
        if(k&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

Use

同上

欧拉函数 Euler

What

1~N中与N互质的数的个数被称为欧拉函数，记为φ(N)

互质：如果gcd(a, b) = 1，则称a,b互质。【注意：a，b不一定都为质数，如4和7】

如果N = p1^c1 * … * pk^ck，则
φ(N) = N * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk) ，
1~N中所有与N互质的数的和等于 N * φ(N) / 2

这样子看会清楚一点吧

欧拉函数

上面一大堆看不懂是不是？我也看不懂哦

举个栗子

24

24=23+31
φ24=24*(2-1)/2*(3-1)/3=8

Code

#include<bits/stdc++.h>
using namespace std;
int n,num;
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d",&num);
		int cnt=0,ans=num;
		for(int i=2;i*i<=num;++i){
			if(num%i==0){
				ans=ans/i*(i-1);
				while(num%i==0)	num/=i;
			}
		}
		if(num>1)	ans=ans/num*(num-1);
		printf("%d\n",ans);
	}
	return 0;
}

筛法求欧拉函数

What

给定一个正整数n，求1~n中每个数的欧拉函数之和。

Code

int primes[N],cnt;
int phi[N];
bool st[N];
long long get_eulers(int n){
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;++j){
            int p=primes[j];
            st[p*i]=true;
            if(i%p==0){
                phi[p*i]=phi[i]*p;break;
            }
            phi[p*i]=phi[i]*(p-1);//p*i代表任意一个要筛的数 
        }
    }
    long long res=0;
    for(int i=1;i<=n;++i)   res+=phi[i];
    return res;
}

Use

这里给出一道题：可见的点

欧拉定理

What

若正整数a, n互质，则a^φ(n) ≡ 1 (mod n)，其中 φ(n) 为欧拉函数。

Code

#include<bits/stdc++.h>
using namespace std;
int n,num;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d",&num);
        int cnt=0,ans=num;
        for(int i=2;i*i<=num;++i){
            if(num%i==0){
                ans=ans/i*(i-1);
                while(num%i==0) num/=i;
            }
        }
        if(num>1)   ans=ans/num*(num-1);
        printf("%d\n",ans);
    }
    return 0;
}

Use

求在1~n范围内与n互质的数的总数

费马小定理

What

若p是质数，则对于任意整数a，有a^p ≡ a(mod p)，即a^p%p=a

▶
(a*x)%p=1 a是x的逆元，x是a的逆元

可以认为费马小定理就是欧拉定理的特殊情况

Code

快速幂求逆元

#include<bits/stdc++.h>
using namespace std;
int n; 
int qmi(int a,int k,int p){
    int res=1%p;
    while(k){
        if(k&1) res=(long long)res*a%p;
        a=(long long)a*a%p;
        k>>=1;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    while(n--){
        int a,p;scanf("%d%d",&a,&p);
        if(a%p==0)
            puts("impossible");
        else
            printf("%d\n",qmi(a,p-2,p));
    }
    return 0;
}

Use

求逆元

卢卡斯定理

What

Lucas(n,m)%p=Lucas(n/p,m/p)*C(n%p,m%p)%p

求上式的时候，Lucas递归出口为m=0时返回1

Code

typedef long long LL;
int p;
int qmi(int a,int k){
	int res=1%p;
	while(k){
		if(k&1)	res=(LL)res*a%p;
		a=(LL)a*a%p;
		k>>=1;
	}
	return res;
}
int C(int a,int b){
	if(a<b)	return 0;//不存在的组合数 
	int res=1;
	for(int i=a,j=1;j<=b;i--,j++){
		res=(LL)res*i%p;//这是组合数里一个什么公式emmm
		res=(LL)res*qmi(j,p-2)%p;//乘法逆元
	}
	return res;
}
int lucas(LL a,LL b){
	if(a<p&&b<p)	return C(a,b);
	return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p; 
}

Use

求组合数取模[n和m较大，但是p为素数的时候]

今天搬运过来看看都觉得头秃……高一的我好厉害啊这些都记下来了（悄悄自恋

版权声明：本文为lsqwq原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/lsqwq/p/theory.html