Modular Exponentian

#1

Failing some test cases

#2

@Vikaspal
hello vikas ,
use long long datatype

#3

@aman212yadav I define ll long long and change the return type of the function to ll but even it doesn’t able to compute 1000^1000 return zeroes so Should I go with array to store the digits of the elements ?

#4

Even if we consider the worst case where the value of a = 10^5, b = 10^5, then (a)^b = 10^5000000 so 1 followed by 5lakh zeros which not possible…

#5

@Vikaspal
check this-> https://ide.codingblocks.com/s/207579

here i have changed
result * =a to result=(result%c * a%c )%c

#6

can exblorate your approach?

#7

@Vikaspal

it is a mod property->

(a * b) %c =( a%c * b%c ) % c

some other properties
image

#8

@aman212yadav thanks you so much bro

#9

One thing why you r u calculate this cout << power(a, b,c) % c mod again when we have(a^b)%10 = to the above property

#10

it will work even if u remove that.
it was already there in ur code that whys i didnt change it

#11

okay thanks @aman212yadav

#12

. . . . :+1:. . . . . :+1:

#13

#include
using namespace std;
//#define ll long long
// power calculated now
int power(int a, int b,int c) {
// specail case to work the code nice

if(a==0) {
	return 0;
}
if(b==0) {
	return 1;
}
int result = 1;
for (int i = 0; i < b; i++) {
	result = (result%c* a%c)%c;
}
return result;

}
int main() {
int a, b, c;
cin >> a >> b >> c;
cout << power(a, b,c);
return 0;
}

Still one test case fail. ?

#14

@Vikaspal

remove this comment

#15

@aman212yadav I have to make the function return type ll instead of int , or int result as ll result where is the use?

#16

both will work ,but In general whenever question is related with modulo then better to use long long to avoid overflow

#17

thanks @aman212yadav to be very active
I facing some issue to understand how to decided the array size can you please help me out ?

#18

@Vikaspal
No need to decide array size.

first read n( array size) then declare array as int arr[n];

ex->
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}

for(int i=0;i<n;i++){
cout<<arr[i];
}

}

#19

@aman212yadav no its not like that. I bit confused to understand the constraints.
Suppose we have to gernerate total number of 5000000 prime number se how to decided the prime_sieve[size].
in that case some pos we have 1 in case of prime and other pos have 0 , the total number we have to is large than how should i decide the array size. I have written the code for the array size 100 max.


Hope u got what i want to know?

#20

@Vikaspal
see if we want to know whether 10 is prime number or not using sieve then we need to declare our sieve size atleast of size 11 (0 to 10 indices) right?

Now in the given problem we need to generate 5000 000 prime numbers so first we need to find 5000 000th prime number(last prime number so that we can determine the size of sieve) and then we should declare our sieve size greater than that