paizaラーニング スキルアップ問題集 Aランクレベルアップメニュー JavaScript 最大公約数 べき乗の計算 (paizaランク C 相当) を解いてみた

paizaスキルアップ問題集 Aランクレベルアップメニュー 最大公約数
べき乗の計算 (paizaランク C 相当)

をJavaScriptで解いてみました。

ランクC相当ですが、難易度: 2230 ±30程度となってました。
どこが難しいのか試しに解いてみましたが、入力値1000000000000の時にうまくいきませんでした。

C++やPython3、Rubyの模範解答を参考に、以下のように解答しても、やはり入力値1000000000000で、間違いがありました。

JavaScript

//75点のコード
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

let N = Number(lines[0]);
const M = 1000003;
let ans = 1;
let pow = 2;

while (0 < N) {
    if (N & 1 === 1) {
        ans = (ans * pow) % M;
    }
    pow = (pow * pow) % M;
    N >>= 1;//ここがうまくいっていない
}
console.log(ans);

どこでつまづいているのか調べたところ、

JavaScript

N >>= 1;

です。
どうやら入力値が大き過ぎて、ビット演算>>がうまくいっていないようです。

解決策として、BigIntを使ってみました。

BigInt は(中略)大きすぎて number プリミティブで表すことができない数を、表現したり操作したりするために使用します。
整数リテラルの末尾に n を追加するか、 BigInt() コンストラクターを呼び出し、整数値または文字列値を与えることで生成することができます。

参照

JavaScript

 N = Number(BigInt(N) >> 1n);

これを使って以下のように解答したところ、無事100点が取れました。

JavaScript

//100点のコード
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

let N = Number(lines[0]);
const M = 1000003;
let ans = 1;
let pow = 2;

while (0 < N) {
    if (N & 1 === 1) {
        ans = (ans * pow) % M;
    }
    pow = (pow * pow) % M;
    N = Number(BigInt(N) >> 1n);//改善箇所
    
}
console.log(ans);

JavaScriptの問題で、ランクがDやC相当にもかかわらず、難易度が高い場合、とても大きな数の処理でうまくいかない場合があるようです。
よろしければ参考にしてください。

---

また、補足ですが、BigIntやビット演算子>>を使わずに、仕組みだけ参考にして解いてみました。
Nを.toString(2)で二進数の文字列に変換して、
その末尾から順に"0"か"1"を判定していきます。
"1"ならば、powを掛けて、mで除き、余りを残します。
文字列なら大きな数値も誤差なく扱えます。

JavaScript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const N = Number(lines[0]).toString(2);
const m = 1000003;
let ans = 1;
let pow = 2;

for (let i = N.length - 1; i >= 0; i--) {
    if (N[i] === "1") {
        ans = (ans * pow) % m;
    }
    pow = (pow * pow) % m;
}
console.log(ans);