exgcd模板

\(ax+by\)
\(=gcd(a,b)\)
\(=gcd(b,a%b)\)
\(=gcd(b,a-(a/b)*b)\)
\(=bx'+(a-(a/b)*b)y'\)
\(=ay'+(x'-(a/b)y')b\)

\(x=y'\)
\(y=x'(a/b)y\)


#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int> exgcd(int x,int y)
{
    if(x==1&&y==0)
    return make_pair(x,y);
    pair<int,int> ans=exgcd(y,x%y);
    return make_pair(ans.second,ans.first-(x/y)*ans.second);
} 
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    pair<int,int> ans=exgcd(a,b);
    printf("%d\n",(ans.first%b+b)%b);
    return 0;
}
全部评论

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
今天 11:42
江西农业大学 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务