Fast Power Mod Function

Fast Power Mod Function

Hard Programming Interview Algorithms 17 views
Explanation Complexity

Problem Statement

We have {x}.

Input Format

One line: a b m.

Output Format

One integer ans.

Example

2 10 1000
24

Constraints

0

Input / Output Format

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

Examples

Input:
2 10 1000
Output:
24

Example Solution (Public)

Programming Interview 
import sys
p=sys.stdin.read().strip().split()
if len(p)<3: sys.exit(0)
a=int(p[0]); b=int(p[1]); m=int(p[2])
def modpow(x,y,mod):
  x%=mod
  res=1%mod
  while y>0:
    if y&1:
      res=(res*x)%mod
    x=(x*x)%mod
    y//=2
  return res
sys.stdout.write(str(modpow(a,b,m)))

Official Solution Code

import sys
p=sys.stdin.read().strip().split()
if len(p)<3: sys.exit(0)
a=int(p[0]); b=int(p[1]); m=int(p[2])
def modpow(x,y,mod):
  x%=mod
  res=1%mod
  while y>0:
    if y&1:
      res=(res*x)%mod
    x=(x*x)%mod
    y//=2
  return res
sys.stdout.write(str(modpow(a,b,m)))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.