===== 64bit整数計算 ======

Javascriptでは数値型は64bit実数として扱われるため、整数としては2の53乗までしか扱うことができません。
通常の利用範囲ではこの精度で困ることはあまりないのですが、AtCoderでは64bit整数を扱えることを前提とした問題がよくでるので対策が必要です。

とりあえず64bit整数を16bit整数4個の変数で処理するクラスを作成しました。
ちなみに32bit整数2個にしなかったのは途中の計算で桁あふれを考慮しなくてもいいようにするためです。

<code>
function UInt64(value) {
    var uint64 = Object.create(UInt64.prototype);
    uint64._wordArray = new Array(4);

    uint64.set(value);

    return uint64;
}

UInt64.compare = function(a, b) {
    for (var i = a._wordArray.length; i >= 0; i++) {
        if (a._wordArray[i] > b._wordArray[i]) {
            return 1;
        }
        else if (a._wordArray[i] < b._wordArray[i]) {
            return -1;
        }
        else {
        }
    }
    return 0;
};

UInt64.prototype.set = function(value) {
    var div = 0;

    if (UInt64.prototype.isPrototypeOf(value)) {
        for (var i = 0; i < this._wordArray.length; i++) {
            this._wordArray[i] = value._wordArray[i];
        }
    }
    else if (typeof value == 'number') {
        div = 1;
        for (var i = 0; i < this._wordArray.length; i++) {
            this._wordArray[i] = (Math.floor(value / div) & 0xFFFF);
            div *= 0x10000;
        }
    }
    else {
        for (var i = 0; i < this._wordArray.length; i++) {
            this._wordArray[i] = 0;
        }
    }
};

UInt64.prototype.add = function(value) {
    var prevCarry = 0;
    var carry = 0;

    for (var i = 0; i < this._wordArray.length; i++) {
        carry = (((this._wordArray[i] + value._wordArray[i] + prevCarry) & 0xFFFF0000) >>> 16);
        this._wordArray[i] = ((this._wordArray[i] + value._wordArray[i] + prevCarry) & 0xFFFF);
        prevCarry = carry;
    }

    return this;
};

UInt64.prototype.multiply = function(value) {
    var prevCarry = 0;
    var carry = 0;
    var prod = UInt64(0);

    for (var i = 0; i < this._wordArray.length; i++) {
        prevCarry = 0;
        for (var j = 0; j < value._wordArray.length; j++) {
            if (i + j >= prod._wordArray.length) {
                break;
            }

            carry = (((this._wordArray[i] * value._wordArray[j] + prevCarry + prod._wordArray[i + j]) & 0xFFFF0000) >>> 16);
            prod._wordArray[i + j] = ((this._wordArray[i] * value._wordArray[j] + prevCarry + prod._wordArray[i + j]) & 0xFFFF);
            prevCarry = carry;
        }
    }

    this.set(prod);

    return this;
};

UInt64.prototype.isZero = function() {
    var ret = true;

    for (var i = 0; i < this._wordArray.length; i++) {
        if (this._wordArray[i] > 0) {
            ret = false;
            break;
        }
    }

    return ret;
};

UInt64.prototype.toString = function() {
    var work = UInt64(this);
    var prevMod = 0;
    var mod = 0;
    var str = '';

    if (work.isZero()) {
        str = '0';
    }
    else {
        while (!work.isZero()) {
            mod = 0;
            prevMod = 0;
            for (var i = work._wordArray.length - 1; i >= 0; i--) {
                mod = (work._wordArray[i] + prevMod) % 10;
                work._wordArray[i] = Math.floor((work._wordArray[i] + prevMod) / 10);
                prevMod = mod << 16;
            }

            str = String.fromCharCode('0'.charCodeAt() + mod) + str;
        }
    }

    return str;
};
</code>