Page 1 of 6
Posted: Thu Mar 14, 2002 10:50 pm
by pete
Hi!
Could anyone give test data with answers...
I have no idea why I get WA.
My code is:
#include <stdio.h>
unsigned long int b,p,m,res;
main()
{
while (scanf("%d %d %d",&b,&p,&m)==3)
{
res=1;
while (p>1) {
if (p&0x01==1)
res=((res%m)*(b%m))%m;
b=((b%m)*(b%m))%m;
p=p/2;
}
printf("%dn",((res%m)*(b%m))%m);
}
}
Thanks.
Posted: Fri Mar 15, 2002 3:26 am
by Stefan Pochmann
Continue the loop until p is zero. Don't change your result after the loop.
Posted: Tue May 21, 2002 6:13 am
by Subeen
there is a good and interesting algorithm for solving this problem.
u can find it in any good algorithms book.
check it out.
What's the idea?
Posted: Tue May 21, 2002 1:41 pm
by jpfarias
Hi, Pete!
Can u tell me what's the idea behind your code?
I can't figure out how to solve this problem... Did u used any MOD property?
Thanx in advance!!!
Jo
Posted: Wed May 22, 2002 1:22 am
by Stefan Pochmann
Subeen: I used the same algorithm as pete did above. Can you tell us more about your algorithm, for example what it's name is? Otherwise it's hard to find what you mean...
jpfarias: pete basically just calculates it with the method of repeated squaring and uses mod everywhere to keep the intermediate results low.
Repeated squaring works like this: Imagine you want to calculate b^42. You could multiply 42 b's together, but that's slow. This is better:
b^42 = b^2 * b^8 * b^32
That's only 3 multiplications after you get the parts by
b^2 = b*b
b^4 = (b^2)^2
b^8 = (b^4)^2
b^16 = (b^8)^2
b^32 = (b^16)^2
So you start with b and then repeatedly multiply it with itself.
374 - I can't find the wrong
Posted: Wed May 22, 2002 6:52 pm
by mark00lui
[c]
Code: Select all
#include<stdio.h>
int main(void)
{
/* R = B^P mod M */
unsigned long B=0, P=0;
unsigned int M=0;
while(3==scanf("%d %d %d", &B, &P, &M))
{
int mod=1, i=0;
if(0==B%M) //best case
{
printf("0\n");
continue;
}
else if(B>M) //let B < M
B%=M;
while(1<P)
{
if(1==P%2)
{
mod*=B;
if(mod>M)
mod%=M;
}
P/=2;
B*=B;
if(B>=M) // let B < M
B%=M;
}
if(1!=mod)
mod=(mod*B)%M;
else
mod=B;
printf("%d\n", mod);
}
return 0;
}
[/c]
Posted: Wed May 22, 2002 7:24 pm
by Fresh
What's the problem? PE, TLE, WA? Dont just send the code.
-novice
Posted: Thu May 23, 2002 4:03 am
by mark00lui
sorry
it is WA
Found Your mistake !!
Posted: Thu May 23, 2002 3:34 pm
by cyfra
Hi!
I have found your mistake...
It is rather stupid one ....
You have to look what will happen when P=0...
Than the answer should be 1 (except when the M=1 then it should be 0)
So try to change it and you will have AC..
Good Luck
Posted: Fri May 24, 2002 11:32 am
by mark00lui
I got it!!!
Posted: Sat Jul 13, 2002 11:19 pm
by Subeen
Stefan...
The following procedure computes a^c mod n as c is increased by doublings and incrementations from 0 to b.
Modular_Exponentiation ( a, b, n )
{
c = 0
d = 1
let {bk, bk-1, …, b0} be the binary representation of b
for i = k downto 0
do c = 2 * c
d = (d * d) mod n
if bi = 1
then c = c + 1
d = (d * a) mod n
return d
}
/* The algorithm is collected from Cormen’s Intro. To Algo. */
Subeen.
Posted: Sun Jul 14, 2002 4:50 pm
by Stefan Pochmann
I doubt that this is from the book. There are way too many mistakes. For example, c is never really used, only to change its own value. That doesn't make sense.
Posted: Tue Jul 16, 2002 4:07 pm
by Subeen
but this is from this book. if u have any doubt then u can check it out.
Posted: Wed Jul 17, 2002 12:10 am
by gvcormac
Sure enough, it is from CLR, essentially as presented.
"c" is just a useless variable they use in explaining the algorithm.
Posted: Wed Jul 17, 2002 7:13 pm
by Stefan Pochmann
Ok, I see. Sorry then... That unnecessary extra c stuff confused me. Also, you said sth like "The following procedure computes ac mod n [...]". This is a partly wrong (It's no multiplication, but an exponentiation) and partly counter-intuitive (It computes (a^b)%n, not (a^c)%n) description. I know now how you meant it, but it's still a bit confusing. Sorry again...