## 374 - Big Mod

Moderator: Board moderators

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### help me now

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]

MAXX^FACTOR
New poster
Posts: 7
Joined: Mon Sep 16, 2002 7:29 am
Location: EARTH.ASIA.TAIWAN.TAIPEI
Contact:

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

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

gaugui
New poster
Posts: 3
Joined: Wed Jul 23, 2003 7:41 am

### Runtime Error (SIGSEGV) 374

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]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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. Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 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);
}
}
zubair-CUET old sailor

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### #374

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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

neo_tohin
New poster
Posts: 5
Joined: Wed Dec 31, 2003 11:24 am
Contact:

### I don't understand your code

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 Live to die

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

### WA :(((

(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]

neo_tohin
New poster
Posts: 5
Joined: Wed Dec 31, 2003 11:24 am
Contact:

### little brother come to help

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
Live to die