昨天还有今天，蒟蒻遨游在数论的海洋中无法自拔。

今日有空，我就好好整理一下近期恶补的数论知识；

首先，让我们从最基础的开始：

1.约数还有素数~~~~~

求约数大家应该都会用最基础的欧几里得算法来求的两数的最大公约数

求素数大家也都会用埃氏筛法或者线性筛法求得，蒟蒻就不赘述了

2.拓展欧几里得算法

求逆元+求同余方程+求不定方程 这小东西太有用了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int x,y;
 4 inline int read(){
 5     static char ch;
 6     int res=0,sign=1;
 7     while((ch=getchar())<'0'||ch>'9'){
 8         if(ch=='-') sign=-1;
 9     }
10     res=ch-'0';
11     while((ch=getchar())>='0'&&ch<='9'){
12         res=res*10+ch-'0';
13     }
14     return res*sign;
15 }
16 int exgcd(int a,int b,int &x,int &y){
17     if(b==0){
18         x=1;
19         y=0;
20         return a;
21     }
22     int d=exgcd(b,a%b,x,y);
23     int tx=x;
24     x=y;
25     y=tx-a/b*y;
26     return d;
27 }
28 int  main(){
29     int a,b;
30     a=read(),b=read();
31     for(register int i=1;i<=a;i++){
32         if(exgcd(i,b,x,y)!=1){
33         printf("-1\n");
34     }else{
35         x=(x%b+b)%b;
36         printf("%d\n",x);
37         }
38     }
39     return 0;
40 }

这就是一个经典的求解逆元的方法，同时也可以求出ax+by=c的一组解；

当且仅当c是gcd(a,b)的倍数的时候方程有整数解；

在求两数最大公约数同时求得ax+by=gcd(x,y)的一组整数解，再求的ax+by=c的解

 

 就是这样的~~

2.逆元

三种方法：拓展欧几里得，费马小定理，线性地推

费马成立是m为素数的时候，a的逆元为a的m-2次方，用快速幂即可

线性是有式子:inv[i]=(p-p/i)*inv[p%i]%p;(inv[1]=1)

线性最快O(n)，拓欧几里得O(n log n);

3.欧拉函数φ（n）=∏(小于n的素数p)(1-1/p)（应该是吧）

4.先咕着