Page 2 of 2
Re: 10843 - Anne's game
Posted: Mon Dec 01, 2008 6:03 pm
by mf
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.
Re: 10843 - Anne's game
Posted: Mon Dec 01, 2008 6:41 pm
by Articuno
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
]
Re: 10843 - Anne's game
Posted: Mon Dec 01, 2008 6:51 pm
by Articuno
Thanks mf for your info. I didn't know about that. Now i understand. Thanks again.
Re: 10843 - Anne's game
Posted: Tue Dec 02, 2008 9:22 am
by abid_iut
thankx Articuno
now I understand and got AC.
thaknx for ur help
Re: 10843 - Anne's game
Posted: Sat Dec 06, 2008 5:23 pm
by zobayer
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