374 - Big Mod

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

374 WA!

Post by oulongbin » Thu Aug 12, 2004 3:15 pm

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:

Post by Minilek » Mon Aug 16, 2004 4:02 am

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

Post by oulongbin » Tue Aug 17, 2004 5:38 am

thank you very much!
i got AC now ! :D

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

#374 Big Mod TLE???

Post by Morning » Mon Sep 27, 2004 5:13 pm

[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
Location: Dhaka, Bangladesh

Post by Junayeed » Mon Sep 27, 2004 7:12 pm

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

Post by Morning » Mon Sep 27, 2004 7:15 pm

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Sep 28, 2004 7:30 am

[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. :wink:

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Tue Sep 28, 2004 8:17 am

Oh my god,thanks so much sohel,i don't realize it will take such a great affact :oops:
"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

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

374(Big mod) TLE Helpppppppppppmeeeeeeeee

Post by J&Jewel » Mon Feb 07, 2005 12:40 pm

#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;
}
I hate Wrong Answer!

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Feb 07, 2005 5:27 pm

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

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

Post by murkho » Fri Jul 15, 2005 6:03 am

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!

Post by Salman » Mon Aug 29, 2005 1:39 pm

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

Post by roticv » Tue Aug 30, 2005 11:18 am

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

Thanks

Post by Salman » Wed Aug 31, 2005 9:14 am

Thanks I got AC

deliric01
New poster
Posts: 2
Joined: Wed Apr 19, 2006 8:05 pm

Post by deliric01 » Wed Apr 19, 2006 8:10 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
  readln (b); readln (p); readln (m); r:=1;
  if b<>0 then begin
   r:=bigmod(b,p,m);
   writeln (r);
  end;
 end;
end.

Post Reply

Return to “Volume 3 (300-399)”