Page 3 of 6
374 WA!
Posted: Thu Aug 12, 2004 3:15 pm
by 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]
Posted: Mon Aug 16, 2004 4:02 am
by 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.
Posted: Tue Aug 17, 2004 5:38 am
by oulongbin
thank you very much!
i got AC now !
#374 Big Mod TLE???
Posted: Mon Sep 27, 2004 5:13 pm
by 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?
Posted: Mon Sep 27, 2004 7:12 pm
by Junayeed
Use Square and Multiply Method.
Best of luck.
Posted: Mon Sep 27, 2004 7:15 pm
by Morning
can u tell me something more about the "Square and Multiply Method"?
i don't know it very much
Posted: Tue Sep 28, 2004 7:30 am
by 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.
Posted: Tue Sep 28, 2004 8:17 am
by Morning
Oh my god,thanks so much sohel,i don't realize it will take such a great affact
374(Big mod) TLE Helpppppppppppmeeeeeeeee
Posted: Mon Feb 07, 2005 12:40 pm
by 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;
}
Posted: Mon Feb 07, 2005 5:27 pm
by 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
>>374 -Run time error, need help..
Posted: Fri Jul 15, 2005 6:03 am
by 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;
}
TLE 374 Big MOd!
Posted: Mon Aug 29, 2005 1:39 pm
by Salman
Posted: Tue Aug 30, 2005 11:18 am
by 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;
}
}
Thanks
Posted: Wed Aug 31, 2005 9:14 am
by Salman
Thanks I got AC
Posted: Wed Apr 19, 2006 8:10 pm
by 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.