清北学堂part2

今天的内容分为两部分,能听懂的和听不懂的...

整一整当前阶段(oi)非常重要的知识点,扩展欧几里得,

其他的不是不重要,只是代码实现效果不很好

代码:

#include<bits/stdc++.h>
using namespace std;
int x,y;
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=;
y=;
}
else{
exgcd(b,a%b,x,y); //思路与辗转相除相似
int t=x;
x=y;
y=t-(a/b)*y;
}
}
int a,b;
int main(){
cin>>a>>b;
exgcd(a,b,x,y); //可求解ax与1 (mod b)或ax+by=1
if(x<) x+=b;
cout<<x;
return ;
}

exgcd求出ax+by=1解后,也可以将x*c%b作为ax+by=1的解,其用途十分广泛

上一篇:sql三维数据


下一篇:java框架篇---struts之文件上传和下载