374 - Big Mod

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

[Stefan Pochmann]

Continue the loop until p is zero. Don't change your result after the loop.

[Subeen]

there is a good and interesting algorithm for solving this problem.
u can find it in any good algorithms book.
check it out.

[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

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

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

[Fresh]

What's the problem? PE, TLE, WA? Dont just send the code.

-novice

[mark00lui]

sorry

it is WA

[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

[mark00lui]

I got it!!!

[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, &#8230;, 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&#8217;s Intro. To Algo. */

Subeen.

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

[Subeen]

but this is from this book. if u have any doubt then u can check it out.

[gvcormac]

Sure enough, it is from CLR, essentially as presented.

"c" is just a useless variable they use in explaining the algorithm.

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