## 374 - Big Mod

Moderator: Board moderators

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 374 WA!

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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
thank you very much!
i got AC now ! Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

### #374 Big Mod TLE???

[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?
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Use Square and Multiply Method.

Best of luck.
Junayeed

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
can u tell me something more about the "Square and Multiply Method"?
i don't know it very much
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
[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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
Oh my god,thanks so much sohel,i don't realize it will take such a great affact "Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:

### 374(Big mod) TLE Helpppppppppppmeeeeeeeee

#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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
your algorithm is not sufficient enough

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
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

### >>374 -Run time error, need help..

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
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

### TLE 374 Big MOd!

How to overcome TLE?

Code: Select all

``````removed after AC

``````
Last edited by Salman on Sun Sep 25, 2005 9:40 am, edited 1 time in total.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

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
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

### Thanks

Thanks I got AC

deliric01
New poster
Posts: 2
Joined: Wed Apr 19, 2006 8:05 pm
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