Page 2 of 6

### help me now

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

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

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
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
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
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
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
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
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
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
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
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;

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
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:=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;
if p=0 then begin writeln(1);goto 1;end;
make;
solve;
writeln(b);
1:
end;
end.[/pascal]

### I don't understand your code

Posted: Wed Jan 07, 2004 12:24 pm
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
(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

Code: Select all

``mods: array [0 .. 31] of integer;``
that contain R for P=2^0, 2^1, .. 2^31.
2) create

Code: Select all

``bi: array [0 .. 31] of boolean;``
- P in BINARY.
3)

Code: Select all

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

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:=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:=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
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
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