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

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

help me now

Post by ec3_limz » Tue Aug 13, 2002 1:19 pm

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]

User avatar
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???

Post by MAXX^FACTOR » 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;
}

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

Runtime Error (SIGSEGV) 374

Post by gaugui » 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]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » 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
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

Post by Per » 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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » 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
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

Post by Per » 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).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » 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
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

Post by Per » 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. :)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » 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
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

Post by zubair » 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[0];

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

Post by Eduard » Tue Dec 09, 2003 9:33 pm

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]
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
Location: Bangladesh
Contact:

I don't understand your code

Post by neo_tohin » Wed Jan 07, 2004 12:24 pm

Sorry brother me also getting tl. :cry:
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 :lol:
Live to die

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

WA :(((

Post by pavelph » 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 :wink:

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

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

little brother come to help

Post by neo_tohin » 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
Live to die

Post Reply

Return to “Volume 3 (300-399)”