【最大公約数】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ランクレベルアップメニュー】

解答例

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

解答例

シェアする

関連投稿

【日付セット】連休を伸ばす2 (paizaランク A 相当) 解答例 – PHP編【paiza】

【PHP】ファイルから一行分のデータを取得する関数「fgtes()」

【五目並べ】STEP: 5 五目並べ（斜め） (paizaランク C 相当) 解答例 – PHP編【Bランクレベルアップメニュー】

【早解13】満員電車の乗車率(paizaランク D 相当) 解答例 – PHP編【Dランク早解きセット】

【へび】STEP: 6 時刻に伴う移動 (paizaランク A 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

【整数の行入力】FINAL問題 【整数の行入力】1,000行の整数の入力 (paizaランク D 相当) – PHP編【標準入力メニュー】

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

【整数の行入力】FINAL問題【整数の行入力】1,000行の整数の入力 (paizaランク D 相当) – PHP編【標準入力メニュー】

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