374 - Big Mod

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

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

[serur]

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

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

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

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

[newton]

as for macro declaration

Code: Select all

#define square(n) (n)*(n)

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

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

[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;
}

[andmej]

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;
}

[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;
}

[mf]

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

[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;
}

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

[dadai]

Ohhhhhhhhhhhhhhhhhhh!!!

Thanks for your help!!
It finally accepted.

Your advice is exactly what I meet.
Thanks too much!!