数论-裴蜀定理、拓展欧几里得（exgcd）

裴蜀定理

对于任意正整数$a$,$b$,那么一定存在非零整数$x$,$y$,使得$ax+by=gcd(a,b)$

exgcd

推导过程：

#include<bits/stdc++.h>
using namespace std;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;
}
int main(){
    int t;cin>>t;while(t--){
    int a,b,x,y;scanf("%d%d",&a,&b);exgcd(a,b,x,y);printf("%d %d\n",x,y);}}

线性同余方程求解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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;
}
int main(){
    int t;cin>>t;while(t--){
    int a,b,m,x,y;scanf("%d%d%d",&a,&b,&m);int d=exgcd(a,m,x,y);if(b%d) cout<<"impossible"<<endl; else printf("%d\n",(ll)x*(b/d)%m);}}