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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Apr 19, 2006 9:08 pm

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
New poster
Posts: 2
Joined: Wed Apr 19, 2006 8:05 pm

Post by deliric01 » Fri Apr 21, 2006 7:36 pm

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Fri Apr 21, 2006 8:22 pm

No, you are mistaken. BINARY REPRESENTATION AND "Divide et impera" technique.
Last edited by serur on Sat Apr 14, 2012 3:36 pm, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Fri Apr 21, 2006 9:38 pm

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...
Last edited by serur on Sat Apr 14, 2012 3:36 pm, edited 1 time in total.

anala_sridhar
New poster
Posts: 4
Joined: Thu Jul 08, 2004 12:53 pm
Contact:

374 - error

Post by anala_sridhar » Mon Nov 27, 2006 3:29 pm

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


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

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Feb 03, 2007 3:54 pm

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!

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Feb 03, 2007 4:28 pm

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Thu Feb 15, 2007 11:43 pm

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
New poster
Posts: 13
Joined: Wed May 16, 2007 12:39 am

Post by Schultz » Thu May 17, 2007 5:33 pm

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

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Fri Feb 08, 2008 4:07 am

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;
}
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

dadai
New poster
Posts: 5
Joined: Thu Feb 21, 2008 5:25 am

374, Time limit exceeded

Post by dadai » Fri Feb 22, 2008 2:12 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 374, Time limit exceeded

Post by mf » Fri Feb 22, 2008 2:46 pm

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

dadai
New poster
Posts: 5
Joined: Thu Feb 21, 2008 5:25 am

Post by dadai » Fri Feb 22, 2008 5:01 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Feb 22, 2008 5:09 pm

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.
Last edited by mf on Fri Feb 22, 2008 5:21 pm, edited 1 time in total.

dadai
New poster
Posts: 5
Joined: Thu Feb 21, 2008 5:25 am

Post by dadai » Fri Feb 22, 2008 5:19 pm

Ohhhhhhhhhhhhhhhhhhh!!!

Thanks for your help!!
It finally accepted.

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

Post Reply

Return to “Volume 3 (300-399)”