## 10843 - Anne's game

Moderator: Board moderators

### Re: 10843 - Anne's game

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.
mf
Guru

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

### Re: 10843 - Anne's game

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

### Re: 10843 - Anne's game

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

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10843 - Anne's game

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/
abid_iut
Learning poster

Posts: 80
Joined: Wed Jul 16, 2008 7:34 am

### Re: 10843 - Anne's game

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

@@ 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.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm