374  Big Mod
Moderator: Board moderators
help me now
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]
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]

 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==1B==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
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,p1,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]
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,p1,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]

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
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 squareandmultiplythingy. 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).
I'm guessing you're talking about the same algorithm as me, the standard squareandmultiplythingy. 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).

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
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 32bit integers, the limit isn't even defined and we can't really state anything about the time complexity.
Sorry, I know I'm pedantic.
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 32bit integers, the limit isn't even defined and we can't really state anything about the time complexity.
Sorry, I know I'm pedantic.

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
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_char1;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[strln1]=res;
for(i=strln2;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);
}
}
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_char1;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[strln1]=res;
for(i=strln2;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);
}
}
zubairCUET old sailor
#374
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[i1] mod 2=0 then a:=a[i1] div 2 else a:=a[i1]1;
until a=1;
number:=i;
end;
procedure solve;
begin
b[number]:=n mod m;
for i:=number1 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]
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[i1] mod 2=0 then a:=a[i1] div 2 else a:=a[i1]1;
until a=1;
number:=i;
end;
procedure solve;
begin
b[number]:=n mod m;
for i:=number1 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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
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
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

 Learning poster
 Posts: 57
 Joined: Wed Dec 10, 2003 7:32 pm
 Location: Russia, SaintPetersburg
WA :(((
I think you wanted to say that (m*m) mod p = (m mod p * m mod p) mod p(m*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;
2) create
Code: Select all
bi: array [0 .. 31] of boolean;
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[0]:=1;
for i:=1 to max do st2:=2*st2[i1];
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[i1])) 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:=nst2; 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
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^11) 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
0^0 is undefined cause we could not decide(0/0 means 0^11) 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