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]
- 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;
}
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]
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]
-
- 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 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).

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

-
- 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_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);
}
}
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
#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[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]
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
http://acm.uva.es/cgi-bin/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, Saint-Petersburg
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[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]
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
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