10843 - Anne's game

[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.

[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 ]

[Articuno]

Thanks mf for your info. I didn't know about that. Now i understand. Thanks again.

[abid_iut]

thankx Articuno
now I understand and got AC.
thaknx for ur help

[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