题解

44 条题解

  • 0
    @ 2013-04-30 10:06:36

    扩展欧几里德算法
    var
    x,y,a,b,d:int64;
    procedure gcd(a,b:int64);
    var
    t:int64;
    begin
    if (a mod b = 0) then
    begin
    x:=0;
    y:=1;
    end
    else
    begin
    gcd(b,a mod b);
    t:=x;
    x:=y;
    y:=t-(a div b)*y;
    end;
    end;
    begin
    readln(a,b);
    d:=b;
    gcd(a,b);
    writeln((x mod d+d) mod d);
    end.

  • 0
    @ 2013-03-16 09:30:36

    刚看了一个小时扩展欧几里得。。。

  • 0
    @ 2012-11-20 17:39:02

    sofa

  • -1
    @ 2017-08-04 08:06:21

    Enjoy.

    #include<cstdio>
    #define LL long long
    using namespace std;
    LL A,B,X,Y;
    LL ExGcd (LL a,LL b,LL &x,LL &y) {  
        
        if (!b) {x=1,y=0;return a;}
        int as=ExGcd(b,a%b,x,y);
        int t=x;x=y;y=t-(a/b)*y;
        return as;
        
    }
    int main () {
        
        scanf("%lld%lld",&A,&B);
        LL gcd=ExGcd(A,B,X,Y),lcm=A*B/gcd;
        while(X<0) {X+=lcm/A;Y-=lcm/B;}
        printf("%lld",X);
        return 0;
        
    } 
    

信息

ID
1781
难度
4
分类
数论 点击显示
标签
递交数
3896
已通过
1521
通过率
39%
被复制
13
上传者