Test Case Failing

#1

I don’t if there is a problem in the logic or what but 5 of the test cases are failing. The code is:

#include
using namespace std;
#define ll long long
int main()
{
ll a,b,c;
cin>>a>>b>>c;
ll ans= 1;
for(ll i=0; i<b; i++)
{
ans*=(a%c);
}
cout<<ans%c<<endl;
}

#2

Hey @Divye-Aggarwal-3050062625037589
Logic is correct
Though it will overflow
do it like this

for(ll i=0; i<b; i++)
{
ans*=(a%c);
ans%=c; //added this
}
1 Like
#3

can you kindly explain why we need to add “ans%=c” in the for loop?

#4

say a,b,c are 2,100,5
Now u have to calculate(2^100)%5
now u were calculating (2%5)^100 and finally also taking %5 of ans
which is equivalent to calculating 2^100 first ,which will overflow for any datatype in c++

So to avoid overflow we use property of modulo i.e
(a*b)%c == ((a%c)*(b%c))%c
Now extend it to 3 vars
(a*b*d)%c == ((((a%c)*(b%c))%c)*(d%c))%c
now u can keep extending it to any amoubt of vars

1 Like
#5

Thankyou so much !! I now know the flaw in my logic!!

1 Like