标签：return cout int 欧几里得 namespace cin exgcd 算法 拓展
877. 扩展欧几里得算法 - AcWing题库
878. 线性同余方程 - AcWing题库
#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;
}
else
{
int t= exgcd(b,a%b,y,x);
y-=a/b*x;
return t;
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
int x,y;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;y=0;
return a;
}
else
{
int t=exgcd(b,a%b,y,x);
y-=a/b*x;
return t;
}
}
signed main()
{
int n;
cin>>n;
while(n--)
{
int a,b,m;
cin>>a>>b>>m;
int x,y;
int d=exgcd(a,m,x,y);
if(b%d==0)
{
cout<<(x*b/d%m+m)%m<<endl;
}
else
cout<<"impossible"<<endl;
}
}
标签：return,
cout,
int,
欧几里得,
namespace,
cin,
exgcd,
算法,
拓展
From： https://blog.csdn.net/hui_le4/article/details/140419766