374 - Big Mod

[oulongbin]

Could somebody tell me why it always says TLE?
i think it is all right.

[cpp]
#include <iostream.h>

long bigmod(long b,long p,long m) {
if (p==0)
return 1;
else if (p%2==0)
return (bigmod(b,p/2,m))*(bigmod(b,p/2,m))%m;
else
return ((b%m)*(bigmod(b,p-1,m)%m))%m;
}


int main()
{
long b,p,m;
while(cin>>b>>p>>m)
{
cout<<bigmod(b,p,m)<<endl;
}


return 0;
}

[/cpp]

[Minilek]

your algorithm grows exponentially because you calculate bigmod twice.

[c]
else if (p%2==0)
return (bigmod(b,p/2,m))*(bigmod(b,p/2,m))%m
[/c]

should be

[c]
else if (p%2==0)
return square((bigmod(b,p/2,m)))%m;
[/c]

define the square function somewhere.

or do
[c]
temp = bigmod(b,p/2,m);
return (temp*temp)%m;
[/c]

P.S. Looking at the input constraints I think you have to use long long and not long. (2^31)^2 does not fit into a long. Alternatively, you could set b = b%m before you perform bigmod since we are told that m is small enough so that m^2 < LONG_MAX.

[oulongbin]

thank you very much!
i got AC now !

[Morning]

[cpp]
#include <iostream>
using namespace std;

long bigMod(long b,long p,long m)
{
if (p == 0) return 1;
if (p % 2 == 0)
{
return (bigMod(b,p / 2,m) * bigMod(b,p / 2,m)) % m;
}
else
{
return ((b % m) * bigMod(b,p - 1,m)) % m;
}
}

int main()
{
long b,p,m;
while(cin >> b >> p >> m)
{
cout << bigMod(b,p,m) << endl;
}
return 0;
}
[/cpp]
anyone who can provide me a faster algorithm?

[Junayeed]

Use Square and Multiply Method.

Best of luck.

[Morning]

can u tell me something more about the "Square and Multiply Method"?
i don't know it very much

[sohel]

[c]
long bigMod(long b,long p,long m)
{
if (p == 0) return 1;
if (p % 2 == 0)
{
return (bigMod(b,p / 2,m) * bigMod(b,p / 2,m)) % m;
}
else
{
return ((b % m) * bigMod(b,p - 1,m)) % m;
}
}
[/c]

Take a look at this part of your code:
return (bigMod(b,p / 2,m) * bigMod(b,p / 2,m)) % m;

is there any difference between bigMod(b,p/2,m) and bigMod(b,p/2,m);
So there is no need to call the function twice.

Use something like:
k = bigMod(b,p/2,m);
and then return ( (k%m) * (k%m) ) % m.

This way the program will get AC in 0.00 seconds.

[Morning]

Oh my god,thanks so much sohel,i don't realize it will take such a great affact

[J&Jewel]

#include<stdio.h>
int main()
{
long b,p,m,sum,b1,i;
//freopen("F:\\374.txt","r",stdin);
while(scanf("%ld%ld%ld",&b,&p,&m)==3)
{
sum=1;
b1=b%m;
for(i=0;i<p;i++)
{
sum=sum*b1%m;
}
printf("%ld\n",sum);
}
return 0;
}

[emotional blind]

your algorithm is not sufficient enough
i think this will help you

Code: Select all

long bigmod(long b,long p,long m) {
  if (p == 0)
    return 1;
  else if (p%2 == 0)
    return square(bigmod(b,p/2,m)) % m; // square(x) = x * x
  else
    return ((b % m) * bigmod(b,p-1,m)) % m;
}

take care

[murkho]

pls help a stupid find out why run time error

Code: Select all

#include<stdio.h>


unsigned long   module(unsigned long    b,unsigned long    p,unsigned long    m);
unsigned long    sq(unsigned long   a);

int main()
{
	unsigned long   r,b,p,m;
	//freopen("f:\\374.in","r",stdin);

	while(scanf("%lu %lu %lu",&b,&p,&m) ==3)
	{
	
	if(b > m)
	b = b%m;
	r = module(b,p,m);
	printf("%lu\n",r);

	
	}



	return 0;
}



unsigned long   module(unsigned long  b, unsigned long   p , unsigned long   m)
{

	if(p ==1)
			return b;

	if(p%2 ==0)
			return sq(module(b,p/2,m))%m;
	else 
			return (	(module(b,p-1,m)	%m) * (b%m)%m);



} 



unsigned long  sq(unsigned long  a)
{

	return a*a;

}

[Salman]

How to overcome TLE?

Code: Select all

removed after AC

[roticv]

you are repeating your calculations. Do the following instead

Code: Select all

int bigmod(int b, int p, int m){
	int a;
	if (p == 0)
		return 1;
	if (p%2 == 0){
		a = bigmod(b,p/2,m);
		return (a*a) % m;
	}else{
		return ((b % m) * bigmod(b,p-1,m)) % m;
	}
}

[Salman]

Thanks I got AC

[deliric01]

Could anyone tell me why my code gets WA??

Code: Select all

var r,b,p,m:longint;

function bigmod (var b,p,m:longint):longint;
var rez:longint;
begin
 if p=0 then rez:=1
 else if p mod 2 =0 then begin p:=p div 2; rez:=sqr(bigmod (b,p,m)) mod m; end
      else begin dec (p); rez:=((b mod m)*bigmod (b,p,m) mod m) mod m; end;
 bigmod:=rez;
end;

begin
 while not eof do begin
  readln (b); readln (p); readln (m); r:=1;
  if b<>0 then begin
   r:=bigmod(b,p,m);
   writeln (r);
  end;
 end;
end.