0

a^b modulus k Question: Write a program that calculates bth power of a modulus k. For example, if you are asked to calculate 2^6 mod 7; 6th power of 2 is 64 thus 64 modulus 7 is 1.

Input specification You will be given 3 integers, a, b, and k where b represents the power and k represents the modulus operand and 0 ≤ b ≤ 1000 and 1 < (a and k) ≤ 1000.

Output specification Show just one integer number which is between 0 and k-1.

Sample Input I

2 6 5

Sample Output I

4

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int a, b, k, d;
    cin >> a >> b >> k;

    int poew = pow(a, b);
    d = poew % k;

    cout << d;
}

It works well but it fails at test case 5;

Test Case 5: 
---------- input.txt ---------- 
50 34 31  

---------- pattern.txt ---------- 
28
Community
  • 1
  • 1
o07l
  • 25
  • 4
  • 4
    `Pow` is a method that takes a floating point number. You'll have to use something else to maintain integer precision. Also, 50^34 doesn't fit in an `int`. – Caramiriel May 09 '15 at 09:00
  • Use this to avoid overflow (a * b) mod k == ((a mod k) * (b mod k)) mod k – Richard Critten May 09 '15 at 09:04
  • `pow()` returns a `double`, whose imprecision is probably what's causing your errors. You're approaching the problem wrong; hint: look up Exponentiation By Squaring and make use of the properties of the modulus. – jadhachem May 09 '15 at 09:04
  • 1
    other duplicates: [Calculating pow(a,b) mod n](http://stackoverflow.com/q/8496182/995714), [Modular Exponentiation for high numbers in C++](http://stackoverflow.com/q/2207006/995714), [Modular Exponentiation](http://stackoverflow.com/q/11448658/995714)... – phuclv May 09 '15 at 09:40

1 Answers1

3

You can do this with 32-bit arithmetic. You just have to reduce mod k after every multiplication, to stop the numbers getting too big:

int pow_mod_k (int a, int b, int k) {
    int result = 1 ;
    while (b--) {
       result *= a ;
       result %= k ;
    }
    return result ;
}

As jadhachem points out in a comment, you can make this faster by using a squaring ladder. But for such small numbers, it would hardly be worth it.

TonyK
  • 16,761
  • 4
  • 37
  • 72