374 - Big Mod

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

pete
New poster
Posts: 2
Joined: Thu Mar 14, 2002 2:00 am

Post by pete » Thu Mar 14, 2002 10:50 pm

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Fri Mar 15, 2002 3:26 am

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

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Tue May 21, 2002 6:13 am

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

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

What's the idea?

Post by jpfarias » Tue May 21, 2002 1:41 pm

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed May 22, 2002 1:22 am

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
New poster
Posts: 6
Joined: Wed May 22, 2002 6:49 pm
Contact:

374 - I can't find the wrong

Post by mark00lui » Wed May 22, 2002 6:52 pm

[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
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

Post by Fresh » Wed May 22, 2002 7:24 pm

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

-novice :-?

mark00lui
New poster
Posts: 6
Joined: Wed May 22, 2002 6:49 pm
Contact:

Post by mark00lui » Thu May 23, 2002 4:03 am

sorry

it is WA

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Found Your mistake !!

Post by cyfra » Thu May 23, 2002 3:34 pm

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 :wink:

mark00lui
New poster
Posts: 6
Joined: Wed May 22, 2002 6:49 pm
Contact:

Post by mark00lui » Fri May 24, 2002 11:32 am

I got it!!! :D

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat Jul 13, 2002 11:19 pm

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.
:lol:
Last edited by Subeen on Wed Jul 24, 2002 7:46 am, edited 1 time in total.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sun Jul 14, 2002 4:50 pm

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Tue Jul 16, 2002 4:07 pm

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

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Jul 17, 2002 12:10 am

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

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

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed Jul 17, 2002 7:13 pm

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

Post Reply

Return to “Volume 3 (300-399)”