【最大公約数】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 問題集解答解答例

エッグ

解答例

シェアする

関連投稿

【ロボット暴走】FINAL問題 ロボットの暴走 (paizaランク A 相当) 解答例 – PHP編【クラス・構造体メニュー】

【PHP】PHPで小数点以下の表記を操作する関数「round()」「floor()」「ceil()」

【指定された値の探索】FINAL問題 【指定された値の探索】指定された値の位置 3 (paizaランク D 相当) 解答例 – PHP編【線形探索メニュー】

【n 行の出力】STEP: 3 10 行以内の出力 (paizaランク D 相当) – PHP編【標準出力メニュー】

【PHP】三項演算子の書き方（条件分岐）

【laravel】laravelのバージョンを確認する方法

【ロボット暴走】FINAL問題ロボットの暴走 (paizaランク A 相当) 解答例 – PHP編【クラス・構造体メニュー】

【指定された値の探索】FINAL問題【指定された値の探索】指定された値の位置 3 (paizaランク D 相当) 解答例 – PHP編【線形探索メニュー】