Fast Power Mod

Fast Power Mod

Medium PHP PHP Operators 22 views
Explanation Complexity

Problem Statement

Input a b m. Print (a^b) mod m.

Input Format

One line: a b m.

Output Format

One integer.

Example

2 10 1000
24

Constraints

0

Input / Output Format

Input Format
One line: a b m.
Output Format
One integer.
Constraints
0

Examples

Input:
2 10 1000
Output:
24

Example Solution (Public)

PHP 
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
[$a,$b,$m]=array_map('intval',preg_split('/\\s+/', $inputText));
$res=1%$m; $base=$a%$m; $e=$b;
while($e>0){
  if($e&1) $res=($res*$base)%$m;
  $base=($base*$base)%$m;
  $e >>= 1;
}
echo $res;
?>

Official Solution Code

<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
[$a,$b,$m]=array_map('intval',preg_split('/\\s+/', $inputText));
$res=1%$m; $base=$a%$m; $e=$b;
while($e>0){
  if($e&1) $res=($res*$base)%$m;
  $base=($base*$base)%$m;
  $e >>= 1;
}
echo $res;
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.