## 10843 - Anne's game

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

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

### 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............ abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### 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/

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

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