10843 - Anne's game

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

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10843 - Anne's game

Post by mf » Mon Dec 01, 2008 6:03 pm

Actually, the code

Code: Select all

ans=1;
for(i=1;i<=98;i++)
{
   ans=(ans*100) % 2000000011;
}
will work pretty well, if you choose the right datatype for ans.

32-bit int won't do, because of a possible overflow in ans*100 (2000000010*100 > 2^31), but a 64-bit integer type is fine.


abid_iut,
judge's compiler is 32-bit, so 'int' and 'long' are both 32-bit integers.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10843 - Anne's game

Post by Articuno » Mon Dec 01, 2008 6:41 pm

Well hi Abid, I told u that the formula i gave is a recursive method. U have to use recursion. Try using the formula
in a recursive function not in main(). Well, what u have to do is just like below :

Code: Select all

long long bigmod(long long B,long long P,long long M) //Here pass n as B, n-2 as P and 2000000011 as M
{
	long long r;
	if(P==0) return 1;
	else if(P%2==0)
	{
		r=bigmod(B,P/2,M);
		return ((r%M)*(r%M))%M;
	}
            else
	{
		return ((B%M)*(bigmod(B,P-1,M)%M))%M;
	}
}
Hope now u can do this.


[By the way,there is another problem {No. 374}, where u can use the similar idea.]
Wish u best luck.
[There was a small mistake in my code. It's okay now. I have edited my code. Sorry :-? ]
Last edited by Articuno on Mon Dec 01, 2008 8:11 pm, edited 2 times in total.
May be tomorrow is a better day............ :)

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10843 - Anne's game

Post by Articuno » Mon Dec 01, 2008 6:51 pm

Thanks mf for your info. I didn't know about that. Now i understand. Thanks again. :)
May be tomorrow is a better day............ :)

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 10843 - Anne's game

Post by abid_iut » Tue Dec 02, 2008 9:22 am

thankx Articuno
now I understand and got AC.
thaknx for ur help
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10843 - Anne's game

Post by zobayer » Sat Dec 06, 2008 5:23 pm

Hi Abid,

Why don't you learn successive squaring algorithm? Using the pow() function has no need here. Look at the two following method for computing (b^p)%m efficiently even b, p, m all are quite large.

1st method is recursive and goes as Articuno told you, easy to understand:

Code: Select all

typedef unsigned long long i64;

inline i64 sqr(i64 n)
{
	return n*n;
}

i64 bigmod(i64 b, i64 p, i64 m)
{
	if (p == 0)
		return 1;
	if (p%2 == 0)
		return sqr( bigmod (b,p/2,m)) % m;
	return ((b % m) * bigmod( b,p-1,m)) % m;
}
2nd method is iterative and a bit faster, try to avoid recursion whenever you can:

Code: Select all

typedef unsigned long long i64;

i64 fast_mod_exp(i64 b, i64 p, i64 m)
{
	i64 r = 1;
	while(p>0)
	{
		if(p&1==1) r = (r*b)%m;
		p >>= 1;
		b = (b*b)%m;
	}
	return r;
}
I think it will help you.

@@ ANYBODY TELL ME IF IT IS A SPOILER FOR THIS PROBLEM, I'LL REMOVE IT @@
zobayer_1@live.com
You should not always say what you know, but you should always know what you say.

Post Reply

Return to “Volume 108 (10800-10899)”