基本结论：

费马小定理：若p为质数，则

 欧拉定理：若a,n互质，则

 欧拉函数计算公式：

 

扩展欧几里得算法（Exgcd）

计算不定方程的一组特解。

由贝祖定理，上方程有解当且仅当时有解。代码中exgcd函数求出的是的解。将其乘上c/d即可得到原方程的解。

设x'_,y'为方程的一组特解，则方程通解可表示为：

代码：

int a,b,c,d,t,x,y;
int exgcd(int a,int b,int &x,int &y) {
    if(b == 0) {
        x=1; y=0; return a;
    }
    int dd=exgcd(b,a%b,x,y),xx=x;
    x=y; y=xx-(a/b)*y;
    return dd;
}
int main() {
    a=read(); b=read(); c=read();
    x=0; y=0;
    d=exgcd(a,b,x,y);
    if(c % d) {
        printf("-1\n");
    }
    x=x*c/d; y=y*c/d;
    printf("%d %d ",x,y);
}

对于线性同余方程 ,我们可以将其转化成不定方程来求解

 

乘法逆元

用于将取模时的除法运算转换成乘法运算。即求出中的x.

求法：

1.费马小定理+快速幂

a,p互质时，逆元即为a^p-2(mod p)

2.exgcd

即求解同余方程  

3.线性递推求1~n中每个数的逆元