Power(a, b) not working properly

Question

1.00/5 (1 vote)

See more:

Question:
Your task is to efficiently calculate values a^b modulo 10^9+7.

Note that in this task we assume that 0^0=1.

Can't understand what the line modulo 10^9 + 7 wants to convey;
I think My program of A(power)B is not working for large output values..
but for the small output values it is working correct..

What I have tried:

Header

#include <bits/stdc++.h>
#define MOD 1000000007;
using namespace std;

long long int power(long long int n,int x);

Main function

int main (){
    int T;
    cin >> T;       // no. of testcases..
    for(int i = 0 ; i < T ; i++){       // running the loop for T no. of testcases
        long long int n;
        int x;
        cin >> n;
        cin >> x;
        cout << power(n,x) << '\n';
    }
}

Power function

long long int power(long long int n,int x){
long long int res = 1;
    while(x){
        if(x%2 == 0){
            n = n*n;
            x = x/2;
        }
        else{
            res = res*n;
            x--;
        }
    }
    res = res%MOD;
    return res;
}

Input:

3(Test_Cases)
3 4
2 8
123 123

Expected Output

81
256
921450052

Received Output

81
256
522397166

Posted 25-Nov-22 23:20pm

Parth Vijay

Updated 26-Nov-22 18:18pm

Add a Solution

2 solutions

Solution 3

My Updated Code after reading the 1st Solution

long long int power(long long int n,int x){
long long int res = 1;
    while(x){
        if(x%2 == 0){
            n = n*n;
            n = n%MOD;
            x = x/2;
        }
        else{
            res = res*n;
            res = res%MOD;
            x--;
        }
    }
    return res;
}

Posted 26-Nov-22 18:18pm

Parth Vijay

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Accepted Answer · 2022-11-26T00:52:00

Quote:
Can't understand what the line modulo 10^9 + 7 wants to convey;

It protects you from overflow of 64-bit integers, because:

(A * B) mod C = (A mod C * B mod C) mod C

(see, for instance, Modular multiplication>[^]).

Try

C++

#include <iostream>
#include <cstdint>
using namespace std;

uint32_t powermod(uint32_t a, uint32_t b)
{
  constexpr uint32_t MOD = 1E9+7;

  uint64_t result = 1;
  while ( b--)
  {
    result *= a;
    result %= MOD;
  }
  return static_cast<uint32_t>(result);
}
int main()
{
  uint32_t a[][2]{ {3, 4}, {2, 8}, {123, 123} };


  for ( auto p : a)
  {
    cout << "powermod(" << p[0] << ", " << p[1] << ") = " << powermod(p[0],p[1])<< "\n";
  }

}