What is wrong with my code? i fails only the last test case

#1

#include

using namespace std;

int modulo(int a,int b,int m){

if(b == 1){

	return (a%m)%m;

}

return ((a%m)*modulo(a,b-1,m))%m;

}
int main() {

long long int a,b,m;

cin>>a>>b>>m;

cout<<modulo(a,b,m)<<endl;

return 0;

}

#2
#3

hi @ankit-c11, just declare the return value as long long
refer :- https://ide.codingblocks.com/s/271303

#4

bhaiiya… i seriously don’t understand when to use long long and when not… can you help with some references?

#5

int is of 4 byte and range of values it can support is -2147483648 to 2147483647 which is 10^9 approx
long long int is of 8 byte and range of values it can support is 9223372036854775807 to -9223372036854775808 which is approx 10^19

so when you think there is a value that can result greater than 10^9 then use long long
int , in this question if we have a=10^5 and b=10^5 then a*b needed to be in long long as it can fit in int,
In cases you are unsure , then you can use long long to be on safe side

also , in this question your algo is taking o(b) time , there is a much better way of doing this question and that too in o(log b)
ref :- https://www.geeksforgeeks.org/modular-exponentiation-recursive/?ref=rp

#6

thanks bahiiya :slight_smile: i got the idea of why we use long long… for the algo… i haven’t reached the recursion section yet… i hope after going through it i could devise a better algorithm… thanks for the detailed explanation and additional help :slight_smile: :slight_smile: