gcd.c

#include <stdio.h>
#include <stdlib.h>

/*
 *  a と b の最大公約数を求める関数 gcd
 *  a と b が負の数でも通用する。
 *
 *  ----
 *
 *  これは、以下が自明であることを利用している
 *
 *  gcd(a, b) = gcd(-a, b) = gcd(a, -b) = gcd(-a, -b)
 *
 *  最大公約数を G (G > 0)とし、a = Ga' b= Gb' とすると、a と b の符号
 *  を入れ替えて如何に組み合わせても最大公約数はGとなる
 */
static int gcd(int a, int b)
{
    int tmp = 0;

    //   絶対値をとることで、a, b のいずれか、または
    //   両方が負であっても通用するようになる
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        if (b < a) {
            // swap (abs(b) is always bigger than abs(a)
            tmp = a;
            a = b;
            b = tmp;
        }
        //
        // s/%/-/ は正しいが、b と a の値の差が圧倒的に大きい
        // ときにずっと同じ値 a を引きつづけるため、非常に遅い
        //
        // b の方が大きい限り a を引き続けるということは、いず
        // れは a で割った余りを求めることと同義になる。よって
        // b % a の方が圧倒的に速い
        //
        // ※  % 演算子のオペランドが負であったときの結果は処理系
        //     定義であることに注意。だが、ここでは a, b は常に
        //     正になるように補正しているので無問題
        //
        b = b % a;
        printf("a:%d b:%d\n", a, b);
    }
    return a;
}
int main(int argc, char *argv[])
{
    //  no error processing
    printf("gcd is %d\n", gcd(atoi(argv[1]), atoi(argv[2])));
}

./gcj 10000000 1
./gcj 0 100
アカウントをとったついでにいじめてみる

./gcd 4294967295 4294967295