GCD

原理:a=b*q+r1; (a,b)==(b1,r1) )( (a,b)为a,b的最小公约数) 代码如下:

1
2
3
4
5
6
7
int gcd(int a,int b)
{
if(b==0)
return a;
gcd(b,a%b);
}

EXGCD

1
2
3
4
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){x=1;y=0;}
else {exgcd(b,a%b,y,x);y-=(a/b)*x;}
}

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号