【最大公約数】STEP: 2 べき乗の計算 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

【Aランクレベルアップメニュー】 > 【最大公約数】STEP: 2 べき乗の計算 (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。

アルゴリズムの問題は難しいというか、ギミックを知ってないといくら頑張って考えても答えを導くことはできないと感じます(;^ω^)
今回は「繰り返し二乗法」というアルゴリズムを使用します。PHPでのサンプルが見つからなかったので少しアレンジしてます。あんまりいいコードじゃないと思いますが、これで通過できちゃった(;’∀’)
アルゴリズムのギミックも理解できてないですし、このアルゴリズム関連の問題本当難しい…。これがランクCとか…嘘だッ！

解答例

<?php
    $n = trim(fgets(STDIN));
    $m = 1000003;
    $p = 2;
    $counter = 1;
    $ans = 1;
    $pow = array_reverse(str_split(decbin($n)));
    $count = count($pow);

    for($i = 0;$i < $count;$i++){ //繰り返し二重法
        if($pow[$i] == 1){
            $ans = ($ans * $p) % $m;
        }
        $counter++;
        $p = $p * $p % $m;
    }
    echo $ans;
?>

<?php

$n = trim(fgets(STDIN));

$m = 1000003;

$p = 2;

$counter = 1;

$ans = 1;

$pow = array_reverse(str_split(decbin($n)));

$count = count($pow);

for($i = 0;$i < $count;$i++){ //繰り返し二重法

if($pow[$i] == 1){

$ans = ($ans * $p) % $m;

}

$counter++;

$p = $p * $p % $m;

}

echo $ans;

カテゴリー:paiza - レベルアップ問題集

タグ:Aランク Aランクレベルアップメニュー PHP paiza 問題集解答解答例

エッグ

エンジニアゲート

【最大公約数】STEP: 2 べき乗の計算 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

解答例

コメントを残すコメントをキャンセル

解答例

シェアする

関連投稿

【1 行目で与えられる N 個の実数の入力 (large) 】STEP: 1 改行区切りでの N 個の実数の入力 (paizaランク D 相当) – PHP編【標準入力メニュー】

【PHP】ファイルがディレクトリ（フォルダ）か調べる関数「is_dir()」

【PHP】ファイルをコピーする関数「copy()」

【漸化式】FINAL問題 【漸化式】 3項間漸化式 2 (paizaランク B 相当) 解答例 – PHP編【DPメニュー】

【N個の文字列の入力】STEP: 4 2 行目で与えられる N 個の文字列の入力 (large) (paizaランク D 相当) – PHP編【標準入力メニュー】

【文字列処理メニュー】i 文字目の出力 (paizaランク D 相当) 解答例 – PHP編【paiza】

コメントを残す コメントをキャンセル

【漸化式】FINAL問題【漸化式】 3項間漸化式 2 (paizaランク B 相当) 解答例 – PHP編【DPメニュー】

コメントを残すコメントをキャンセル