374 - Big Mod

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

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

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

[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

[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.

[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

[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).

[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

[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.

[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

[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);
}
}

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

[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

[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

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]

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