## 374 - Big Mod

Moderator: Board moderators

pete
New poster
Posts: 2
Joined: Thu Mar 14, 2002 2:00 am
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:
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
Contact:
there is a good and interesting algorithm for solving this problem.
u can find it in any good algorithms book.
check it out. jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### What's the idea?

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?

Jo

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

[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:
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:
sorry

it is WA

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

Hi!

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
New poster
Posts: 6
Joined: Wed May 22, 2002 6:49 pm
Contact:
I got it!!! Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
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. 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:
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
Contact:
but this is from this book. if u have any doubt then u can check it out. gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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:
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...