Page **2** of **6**

### help me now

Posted: **Tue Aug 13, 2002 1:19 pm**

by **ec3_limz**

hey hey hey

please help me

There's something wrong with my recursion, but I can't see anything wrong.

[cpp]#include <stdio.h>

int number, mod;

int recur(int exp) {

if (exp == 0)

return 1;

int v = recur(exp / 2);

v *= v;

if (exp % 2 != 0)

v *= number;

v %= mod;

return v;

}

int main() {

int power;

while (scanf("%d%d%d", &number, &power, &mod) == 3) {

number %= mod;

printf("%d\n", recur(power));

}

return 0;

}[/cpp]

### P374 >>>Time Limit Exceed........How could it be???

Posted: **Mon Sep 16, 2002 7:45 am**

by **MAXX^FACTOR**

Code: Select all

```
I think my method is fast enough..........
However........It arise "TimeLimitExceeded"
Anybody knows why???
My idea is:
5^100 mod 26
=((5^3)^33)*(5^1) mod 26
= ((5^3 mod 26)^33)*(5^1 mod 26) mod 26
=(21^33)*5 mod 26
=X^Y*Z mod 26 ............etc
Repeat until X^Y<26 and Z<26
Then directly calculate the result.
#include <iostream.h>
#include <math.h>
int main()
{
int i,B,P,M,x,y,R;
bool flag,flag2;
while(cin>>B>>P>>M){
flag2=0;
R=1;
if(B==1||B==0)
flag2=1;
while(1){
if(flag2==1)
break;
flag=false;
for(i=1;i<=P;i++)
if(pow(B,i)>=M){
x=P/i;
y=P%i;
R%=M;
flag=true;
break;
}
if(flag==true){
R*=pow(B,y);
B=((int)pow(B,i))%M;
P=x;
}
else
break;
}
R%=M;
if(flag2==1){
if(B==1)
cout<<1%M<<endl;
else
cout<<0<<endl;
}
else
cout<<((int)(pow(B,P)*R))%M<<endl;
}
return 0;
}
```

### Runtime Error (SIGSEGV) 374

Posted: **Wed Jul 23, 2003 11:48 am**

by **gaugui**

mycode

but Runtime Error (SIGSEGV)???/

why

(a * b) mod c = ((a mod c) * (b mod c)) mod c

BP = BP / 2 * BP / 2

BP = BP - 1 * B

[cpp]

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

long big_mod( long b, long p, long m)

{

long c;

if(p==1){

return b%m;

}else{

if(p%2){

c=big_mod(b,p-1,m);

return ((c%m)*(b%m))%m;

}else{

c=big_mod(b,p/2,m);

return ((c%m)*(c%m))%m;

}

}

}

int main()

{

long b,p,m;

while(cin>>b>>p>>m)

{

cout<<big_mod(b,p,m)<<endl;

getchar();

}

return 0;

}

[/cpp][/code]

Posted: **Wed Jul 23, 2003 1:29 pm**

by **Dominik Michniewski**

Using recurrency for this problem in many cases imply TLE (or RTE). Think about B,P,M which can be 0 ....

and BTW. exist algoritm which computes answer in O(1) time

Best regards

DM

Posted: **Thu Jul 24, 2003 12:21 am**

by **Per**

Hm? O(log P) is simple, but how can you do it in O(1)? (Without using an O(M^3) lookup table...)

M can't be 0, btw.

Posted: **Thu Jul 24, 2003 8:15 am**

by **Dominik Michniewski**

Per, think about bits - this is constant value regardless of value of P. (Maybe you talking about it - but why log(P) ? Could you explain me?) No lookup table.

Yes, P can't be zero. But rest could be. And with recurrency and very large values for all parameters we not so fast get answer ....

Best regards

DM

Posted: **Thu Jul 24, 2003 8:59 am**

by **Per**

Well, yeah sure, but if you see it that way, almost any algorithm is O(1), even if it takes O(2^P), so it's not very informative .

I'm guessing you're talking about the same algorithm as me, the standard square-and-multiply-thingy. This algorithm uses O(#bits in P) multiplications and modular reductions. So if you consider the number of bits constant (which as I said maybe is not so informative), this is O(1), but if you consider the asymptotic case with unbounded P, it is O(log P).

Posted: **Thu Jul 24, 2003 1:25 pm**

by **Dominik Michniewski**

Yes, I'm talking about such algorithm.

But I'm not think, that O(2^P) is the same as O(1) when P is input paramater, which talk us range size of input. But I still think, that this algorithm, which is in this meaning O(log(P)), is O(1)

Best regards

DM

Posted: **Fri Jul 25, 2003 12:16 pm**

by **Per**

Maybe not philosophically, but mathematically, if you assume that the number of bits in P (i.e. log_2(P)) is some constant C (i.e. that O(#bits in P) = O(1)), than P must be bounded by some constant 2^C, and 2^P must be bounded by some constant 2^(2^C), hence O(2^P) also becomes O(1).

Ordo notation is about asymptotic growth rate. A bit more formal: by definition, f(n) is O(g(n)) iff lim(n -> inf, f(n)/g(n)) converges. So if we say that the running time T(P) only takes P which fits in 32-bit integers, the limit isn't even defined and we can't really state anything about the time complexity.

Sorry, I know I'm pedantic.

Posted: **Sat Jul 26, 2003 8:35 am**

by **Dominik Michniewski**

OK, you have right, Per - to be padantic it's not bad

I thought about it in other way - but you have right, this kind of solutions have logarithmic time complexity. But in this problem it's very very fast

:)

Best regards

DM

Posted: **Sun Sep 14, 2003 1:32 pm**

by **zubair**

hi,

i don't know why i am getting w/a .can any body give me some sample input to test or tell me what i have missed in my code?

here is my code:

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#define MAX 1000

char *to_nbase(unsigned long number, int base)

{

char digits[MAX],final[MAX];

int which_char = 0;

int i,t;

while (number > 0)

{

digits[which_char] = number % base+'0';

number = number / base;

which_char++;

}

digits[which_char]='\0';

t=0;

for(i=which_char-1;i>=0;i--)

final[t++]=digits*;*

final[t]='\0';

return(final);

}

unsigned long resid(unsigned long a,unsigned long b)

{

unsigned long r;

r=a%b;

return r;

}

void main()

{

unsigned long integer,num;

unsigned long res;

unsigned long temp;

char *newnum;

long m;

unsigned long residue[MAX];

int strln;

int i;

newnum=(char *)malloc(MAX*sizeof(char));

//freopen("374.in","r",stdin);

//freopen("374.out","w",stdout);

while(scanf("%lu %lu %ld",&num,&integer,&m)==3)

{

if(integer>0)

{

newnum=to_nbase(integer,2);

}

else

strcpy(newnum,"0");

strln=strlen(newnum);

res=resid(pow(num,1),m);

residue[strln-1]=res;

for(i=strln-2;i>=0;i--)

{

res=resid(pow(res,2),m);//

residue*=res;*

}

res=residue[0];

for(i=1;i<strln;i++)

{

if(newnum*=='1')*

{

res=resid(res*residue*,m);*

}

}

printf("%lu\n",res);

fflush(stdin);

}

}

### #374

Posted: **Tue Dec 09, 2003 9:33 pm**

by **Eduard**

PLEASE HELP IT GET"S TLE.

my code.

[pascal]program acm374;

label 1;

var a,b:array[1..1000] of longint;

i,j,k,m,n,p,number:longint;

procedure make;

begin

i:=1;

a[1]:=p;

repeat

i:=i+1;

if a[i-1] mod 2=0 then a*:=a[i-1] div 2 else a**:=a[i-1]-1;*

until a*=1;*

number:=i;

end;

procedure solve;

begin

b[number]:=n mod m;

for i:=number-1 downto 1 do

if 2*a[i+1]=a* then b**:=((b[i+1] mod m)*(b[i+1] mod m)) mod m*

else

b*:=((b[i+1] mod m)*(b[number] mod m)) mod m;*

end;

begin

while not eof do

begin

for i:=1 to 1000 do

begin

a*:=0;*

b*:=0;*

end;

read(n,p,m);

readln;

if p=0 then begin writeln(1);goto 1;end;

make;

solve;

writeln(b[1]);

1:

end;

end.[/pascal]

### I don't understand your code

Posted: **Wed Jan 07, 2004 12:24 pm**

by **neo_tohin**

Sorry brother me also getting tl.

but my algorithm is not so big as yours.

check this out man:

(m*m*m)mod p=(m mod p * m mod p)mod p

ha ha ha

### WA :(((

Posted: **Sun Feb 01, 2004 10:55 pm**

by **pavelph**

(m*m*m)mod p=(m mod p * m mod p)mod p

I think you wanted to say that (m*m) mod p = (m mod p * m mod p) mod p

I also as can't get AC for this problem. But my prog work on all my inputs.

But I don't know what output must be for (0, 0, m)

My algorithm have this steps:

1) create

that contain R for P=2^0, 2^1, .. 2^31.

2) create

- P in BINARY.

3)

Code: Select all

```
for i:=0 to 31 do
if bi[i] then R:=(R*mods[i]) mod m;
```

4) R is answer.

Here my code:

[pascal]program acm374; {Big Mod}

const max = 31;

type

{ integer = longint;}

pok = array [0 .. max] of integer;

var b, p, m: integer;

st2: pok;

procedure make_2;

var i: integer;

begin

st2[0]:=1;

for i:=1 to max do st2

*:=2*st2[i-1];*

end;

procedure solve;

var i, res, r, s: integer;

mods: pok;

bi: array [0 .. max] of boolean;

procedure make_mods;

var i: integer;

begin

mods[0]:=r;

for i:=1 to max do

mods*:=(sqr(mods[i-1])) mod m;*

end;

procedure bin(n: integer);

var v, i: integer;

begin

v:=0;

while st2[v]<=n do inc(v); dec(v);

fillchar(bi, sizeof(bi), false);

for i:=v downto 0 do

if n>=st2* then begin n:=n-st2**; bi**:=true; end;*

end;

begin

r:=b mod m;

res:=1;

make_mods;

bin(p);

for i:=0 to max do

if bi* then res:=(res*mods**) mod m;*

writeln(res);

end;

procedure in_put;

begin

readln(b, p, m); readln;

if (b=0) then writeln(b)

else if p=0 then writeln('1')

else solve;

end;

begin

make_2;

while not eof do in_put;

end.[/pascal]

### little brother come to help

Posted: **Sat Feb 07, 2004 2:35 pm**

by **neo_tohin**

As further i know 0^0 is undefined. But i think you should try to use the modulus as 0. try it . the explanation is:

0^0 is undefined cause we could not decide(0/0 means 0^1-1) on the ? area.

0 | 0 | ?

0

------------

0

I think same thing happens to others cases of undefined and infinite. So, i request you to submit your code as the output for this case as 0.

Have a nice dream