Page **4** of **6**

Posted: **Wed Apr 19, 2006 9:08 pm**

by **serur**

Think abot bits and therefore about binary representation,

I solved 374 yeterday using hints from Jan and Michniewski - thank you fellows for your illustrious hints!

On the whole this problem is very-very nice!

Posted: **Fri Apr 21, 2006 7:36 pm**

by **deliric01**

If I am not mistakeing I belive u just told me to change type to int64 and that is what I did but still WA.

Posted: **Fri Apr 21, 2006 8:22 pm**

by **serur**

No, you are mistaken. BINARY REPRESENTATION AND "Divide et impera" technique.

Posted: **Fri Apr 21, 2006 9:38 pm**

by **serur**

Again, Michniewski and Per had a nice talk about 374-BIG MOD somewhere here, their idea is actually smart - without any recursion at all, mere loop...

### 374 - error

Posted: **Mon Nov 27, 2006 3:29 pm**

by **anala_sridhar**

It is the 'Big Mod' (374) problem, i use Java Programming.

everything seems to be normal ...but my code is getting rejected. what cud b the problem.

code removed (frustrated, there are lot other problems to b solved...hence moving forward).

Posted: **Sat Feb 03, 2007 3:54 pm**

by **newton**

i also got AC in 00.002 sec. but is there any algorithm that we can get the mod without recursiving.

Mr Olongbin

After AC you should remove your code from the forum.

always try to represent your code using code tag

Code: Select all

```
[code]...thank you very much!
i got AC now ! ...
```

[/code]

then the program will be more reliable to check for other.

best of luck

newton........................................... simply the best!

Posted: **Sat Feb 03, 2007 4:28 pm**

by **newton**

as for macro declaration

the compiler has to compile the code (n) and (n) twice

in the code

Code: Select all

```
long bigmod(long b,long p,long m) {
if (p == 0)
return 1;
else if (p%2 == 0)
return square(bigmod(b,p/2,m)) % m; // square(x) = x * x
else
return ((b % m) * bigmod(b,p-1,m)) % m;
}
```

bigmod function is called twice more.

so if we chang the code into:

Code: Select all

```
long bigmod(long b,long p,long m) {
if (p == 0)
return 1;
else if (p%2 == 0)
{
long temp=bigmod(b,p/2,m)%m;
return square(temp) % m; // square(x) = x * x
}
else
return ((b % m) * bigmod(b,p-1,m)) % m;
}
```

it will reduce time limit twice more.
is there any wrong with me?

is not this more sufficient algorithm?

best of luck

newton.............................. simply the best

Posted: **Thu Feb 15, 2007 11:43 pm**

by **Vexorian**

To anybody who finds this thread by searching.

The devided and conquer algorithm is correct, but there are 2 captchas:

if m=1 the result should always be 0.

0^0 equals 1.

And finally there is whitespace after the I/O's last test case, so cin.eof() won't be enough.

Posted: **Thu May 17, 2007 5:33 pm**

by **Schultz**

Yes, there is one, but it requires a bit more thought.

Consider

Code: Select all

```
/* calculates a^b mod m */
integer modpow(integer a, integer b, integer m) {
integer p = 1; // such that a0^b0 is always p*a^b
while (b != 0) {
if (b%2 == 0) b/= 2;
else {
b = (b-1)/2;
p = (p*a)%m;
}
a = (a*a)%m;
}
return p%m;
}
```

Posted: **Fri Feb 08, 2008 4:07 am**

by **andmej**

Per wrote: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 can't figure out which algorithm are you talking about. This is the algorithm I used to solve the problem using simple bitwise operations. Is this the one you are talking about? If it is, I can't see why would it run in O(1) time. It depends of the number of digits of the binary representation of

**P**; meaning it takes O(log

**P**) time.

Code: Select all

```
long f(long b, long p, long m){
long mask = 1;
long pow2 = b % m;
long r = 1;
while (mask){
if (p & mask)
r = (r * pow2) % m;
pow2 = (pow2*pow2) % m;
mask <<= 1;
}
return r;
}
```

### 374, Time limit exceeded

Posted: **Fri Feb 22, 2008 2:12 pm**

by **dadai**

Hi, all.

I tried the problem 374,

but I got the "Time limit exceeded".

How can I improve my code?

Also, if I create a array with size 46340,

it become "Runtime error".

#include <stdio.h>

int main()

{

long long int basis=0, p_num=0, m_num=0;

long long int tmp=1;

int i=0, n=0;

while(scanf("%lld %lld %lld", &basis, &p_num, &m_num) == 3) {

tmp = 1;

n = 0;

i = 0;

if(basis%m_num == 0) {

printf("0\n");

continue;

}

do {

tmp *= basis;

tmp %= m_num;

n++;

} while(tmp != 1);

i = (p_num%n);

while(i--) {

tmp *= basis;

tmp %= m_num;

}

printf("%d\n", tmp);

}

return 0;

}

### Re: 374, Time limit exceeded

Posted: **Fri Feb 22, 2008 2:46 pm**

by **mf**

dadai wrote:
do {

tmp *= basis;

tmp %= m_num;

n++;

} while(tmp != 1);

Looks like you're trying here to find n>0, such that B^n = 1 (mod M).

Well, such n doesn't always exist, and your program enters infinite loop. Try B=4, M=6.

How can I improve my code?

Use a better algorithm.

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Posted: **Fri Feb 22, 2008 5:01 pm**

by **dadai**

Thanks for your advice,

I follow the page and change my code.

Now I follow the algorithm,

and work well in my computer.

But I get "Runtime error" when I update.

Is there anything wrong with my code?

#include <stdio.h>

long long int basis, p_num, m_num;

long long int sqrt_alg(long long int tmp)

{

long long int a=0, b=0;

if(tmp == 2) {

b = (basis*basis)%m_num;

return b;

}

else if(tmp&1) {

tmp--;

a = tmp>>1;

b = sqrt_alg(a);

return ((basis%m_num)*b*b)%m_num;

}

else {

a = tmp>>1;

b = sqrt_alg(a);

return (b*b)%m_num;

}

}

int main()

{

long long int tmp=1;

int i=0, n=0;

while(scanf("%lld %lld %lld", &basis, &p_num, &m_num) == 3) {

if(p_num == 0)

printf("1\n");

else if(p_num == 1)

printf("%lld\n", basis%m_num);

else {

tmp = sqrt_alg(p_num);

printf("%lld\n", tmp);

}

}

return 0;

}

Posted: **Fri Feb 22, 2008 5:09 pm**

by **mf**

Well, apparently you haven't put much effort into testing it. It should crash due to stack overflow whenever the two leading bits of P are 11. - in this case at some point there's a call to sqrt_alg(3), followed by sqrt_alg(1), followed by infinitely recursive sqrt_alg(0)...

And by theory of probability it should've taken you just around 2 random tests to discover this on your own.

The proper base case for recursion is: x^0 = 1 % M. Everything boils down to it.

Posted: **Fri Feb 22, 2008 5:19 pm**

by **dadai**

Ohhhhhhhhhhhhhhhhhhh!!!

Thanks for your help!!

It finally accepted.

Your advice is exactly what I meet.

Thanks too much!!