### agent3889's blog

By agent3889, 8 years ago, ,
hey guys i found this book while i search the net. this might be useful for some of you.

http://acm.uva.es/problemset/Art_of_Programming_Contest_SE_for_uva.pdf

• -13

 8 years ago, # | ← Rev. 3 →   +30 Mmm...int gcd(int a, int b) { int r=1; if(a>b) { while ( r!=0) { r=a%b; a=b; b=r; } return a; } else if ( b>a) { while (r!=0) { r=b%a; b=a; a=r; } return b; } else if ( a==b) return a; } I love this book!
•  8 years ago, # ^ | ← Rev. 2 →   0 H-m... ===int gcd(int a, int b){  while ((a > 0) && (b > 0)){      if (a > b) a = a % b;    else b = b % a;   }  return a + b;}===?
•  8 years ago, # ^ | ← Rev. 2 →   +6 NO!int gcd(int x, int y){       return y ? gcd(y,x%y) : x;}
•  8 years ago, # ^ |   -12 Yes! :)
•  8 years ago, # ^ |   +1 int gcd(int a, int b) { while (a) { int c = b % a; b = a; a = c; } return b; } 
•  8 years ago, # ^ | ← Rev. 2 →   +4 Попсово, но всё же...int gcd (int a, int b) {    while (b)         b ^= a ^= b ^= a %= b;    return a;}Кстати, а каким тегом можно обрамить для синтаксической подсветки?
•  8 years ago, # ^ |   0 Unfortunately a ^= b ^= a ^= b doesn't work in Java.
•  8 years ago, # ^ | ← Rev. 3 →   +8 I have used tohtml.comI don't know is there code-highlight tag or not.
•  8 years ago, # ^ | ← Rev. 2 →   +3 Where did you get this snippet? Can't find it in the mentioned book (or the link have changed?)Ah... It is in appendix B... But in chapter 7 there is proper and far shorter implementation... What is this wonderful stuff which the author uses for loading his cigarettes, I wonder?
 » 8 years ago, # |   0 another way.... :)public static int gcd(int a, int b) {        int gcd = 0;        while (a != b) {            if (a > b) {                a -= b;            } else {                b -= a;            }        }        gcd = a;        return gcd;    }
•  » » 8 years ago, # ^ |   +5 This way is far slower, since these repetitious (a -= b) are the same as a %= b, but performed in a/b steps.Since all modern computers perform division operation with the same speed as addition/subtraction it is obvious waste of time.The only worse thing I can think of is: public static int gcd(int a, int b) { int gcd = Math.min(a, b); while (a % gcd != 0 || b % gcd != 0) gcd--; return gcd; } // gcd 
•  » » » 8 years ago, # ^ | ← Rev. 5 →   -9 By the way, gcd with subtraction is only 1.5 times slower in average than gcd with division :)Moreover: long long gcd1(long long a, long long b) { return b ? gcd1(b,a%b) : a; } long long gcd2(long long a, long long b) { while (a != b) { if (a > b) { a -= b; } else { b -= a; } } return a; } int main() { int n, m; cin >> n >> m; long long result = 0; cout<
•  » » » » 8 years ago, # ^ |   +11 try something more interesting, try "2 10.000.000.001"` as input ;-)
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 def gcd(a,b):    r=a%b    while r > 0:a, b, r = b, r, b%r    return b
•  » » » 8 years ago, # ^ |   +16 def gcd(a,b):    while b:        a, b = b, a % b    return a