Code: Select all

`if(d > 1000000000) d /= 1000000000`

And in the end print the first three digits (it's easy in Java, at least it's good for something).

**Moderator:** Board moderators

Code: Select all

`if(d > 1000000000) d /= 1000000000`

And in the end print the first three digits (it's easy in Java, at least it's good for something).

I m getting TLE when using the fast exponentiation method for Leading part alsoDarko wrote:All I did was something like (within the pow function):where d is a double.Code: Select all

`if(d > 1000000000) d /= 1000000000`

If I will myself do hashing, then who will do coding !!!

Code: Select all

```
while (n > Integer.MAX_VALUE)
n /= 1000000000;
```

No I do fast exponentiation now and geting WADarko wrote:I lied, this is what I did:And - how do you get TLE if you do logk operations?Code: Select all

`while (n > Integer.MAX_VALUE) n /= 1000000000;`

If I will myself do hashing, then who will do coding !!!

I got WA

Can anyone give a case where it fails down

#include<iostream>

#include<math.h>

#include<stdio.h>

using namespace std;

double bigMod1(double b,double p)

{

if (p==0)return 1.0;

long pp=(long)p;

if (pp % 2 == 0)

{

double r=bigMod1(b,p/2);

double j=(r*r);

if(j> 1000000000) j /= 1000000000;

return j;

}

else

{

double j=(b*bigMod1(b,p-1));

if(j> 1000000000) j /= 1000000000;

return j;

}

}

long bigMod(long b,long p,long m)

{

if (p==0)return 1;

if (p % 2 == 0)

{

long r=bigMod(b,p/2,m);

return (r*r)%m;

}

else

{

return ((b%m)*bigMod(b,p-1,m))%m;

}

}

int main(){

int n,m,k;

cin>>n;

while(n--){

cin>>m>>k;

long ttt;

ttt=bigMod(m,k,1000);

double mm=m,kk=k;

double lll=bigMod1(mm,kk);

while(lll<100){

lll*=10;

}

char buf1[30];

sprintf(buf1, "%.0Lf", lll);

cout<<buf1[0]<<buf1[1]<<buf1[2];

cout<<"...";

if(ttt<10){

cout<<"00"<<ttt<<endl;

}

else if(ttt<100){

cout<<"0"<<ttt<<endl;

}

else{

cout<<ttt<<endl;

}

}

return 0;

}

Can anyone give a case where it fails down

#include<iostream>

#include<math.h>

#include<stdio.h>

using namespace std;

double bigMod1(double b,double p)

{

if (p==0)return 1.0;

long pp=(long)p;

if (pp % 2 == 0)

{

double r=bigMod1(b,p/2);

double j=(r*r);

if(j> 1000000000) j /= 1000000000;

return j;

}

else

{

double j=(b*bigMod1(b,p-1));

if(j> 1000000000) j /= 1000000000;

return j;

}

}

long bigMod(long b,long p,long m)

{

if (p==0)return 1;

if (p % 2 == 0)

{

long r=bigMod(b,p/2,m);

return (r*r)%m;

}

else

{

return ((b%m)*bigMod(b,p-1,m))%m;

}

}

int main(){

int n,m,k;

cin>>n;

while(n--){

cin>>m>>k;

long ttt;

ttt=bigMod(m,k,1000);

double mm=m,kk=k;

double lll=bigMod1(mm,kk);

while(lll<100){

lll*=10;

}

char buf1[30];

sprintf(buf1, "%.0Lf", lll);

cout<<buf1[0]<<buf1[1]<<buf1[2];

cout<<"...";

if(ttt<10){

cout<<"00"<<ttt<<endl;

}

else if(ttt<100){

cout<<"0"<<ttt<<endl;

}

else{

cout<<ttt<<endl;

}

}

return 0;

}

If I will myself do hashing, then who will do coding !!!

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

Hmm, within the set of (2^32 - 1)*10^7 (approx. 4*10^16) possible input combinations, there will be an expected 40000 such cases, and an equal number of cases that get erroniously rounded down. I know of problems that test special cases with slimmer chances...Cho wrote:I think the 4th to 15th digit can be considered as some sort of pseudo-random number, then the probability that all these digits being 9 is exponentially small.little joey wrote:I also calculated the first three digits using <math.h> and got accepted, but I still have some doubts about precision.

How can we be sure that a 100-million digit number that starts off "123999999999999999999999999..." is not printed as "124..." without doing bigint calculus?

I fixed it now, but the point is - I don't think they looked for nasty test cases. Or they omitted them on purpose - this problem ended up being the easiest problem in the set (judging by the number of AC during the contest).

Hi, I have submitted this problem several times but only managed to get T.L.E. I find the trailing digits by bigmod function and leading digits by fast exponentiation. Followings are the part of my code:
and
Any help is appreciated...

Code: Select all

```
FUNCTION USED TO FIND b^p mod m:
=========================
long long bigmod (long long b, long long p, long long m)
{
if (p == 0)
return 1;
else if (p % 2 == 0)
return (bigmod (b, p / 2, m) * bigmod (b, p / 2, m)) % m;
else
return ((b % m) * bigmod(b, p - 1, m)) % m;
}
```

Code: Select all

```
FUNCTION USED TO FIND base^power:
==========================
long long square (long long n)
{
return n * n;
}
long long fastexp (long long base, int power)
{
long long r;
char digits[10];
if (power == 0)
return 1;
else if (power % 2 == 0)
{
r = (square (fastexp (base, power / 2)));
if (r > BIG)
{
sprintf(digits, "%lld", r);
digits[4] = NULL;
r = atol(digits);
}
return r;
}
else
{
r = (base * ( fastexp (base, power - 1)));
if (r > BIG)
{
sprintf(digits, "%lld", r);
digits[4] = NULL;
r = atol(digits);
}
return r;
}
}
BIG is defined as #define BIG 10000l
Everytime the resulting number gets bigger than BIG, I try to truncate the following digits[taking only the higher ones]. [IS THIS METHOD OKAY TO GET LEADING DIGITS ???]
```

BIG is actually power of 10 here, as you 've mentioned; 10^4 to be precise.10000l ... here. l is the suffix to denote long . Anyway, it is not working for me, I again got TLE after changing the code to divide by BIG.

if p is even you are computing bigmod b, p/2 twice instead of once in each debth of recursion. write something likenymo wrote:Hi, I have submitted this problem several times but only managed to get T.L.E. I find the trailing digits by bigmod function and leading digits by fast exponentiation. Followings are the part of my code:Code: Select all

`FUNCTION USED TO FIND b^p mod m: ========================= long long bigmod (long long b, long long p, long long m) { if (p == 0) return 1; else if (p % 2 == 0) return (bigmod (b, p / 2, m) * bigmod (b, p / 2, m)) % m; else return ((b % m) * bigmod(b, p - 1, m)) % m; }`

long long tmp = bigmod( b, p/2, m ) % m; tmp *= tmp; tmp %= m;

return tmp;

Hi!!!

I think there is a bug in this problem!

Here such input:

1

2 3

I think that answer should be : 008...008, but my accepted programm return 800...008

What do you think about it?

I think there is a bug in this problem!

Here such input:

1

2 3

I think that answer should be : 008...008, but my accepted programm return 800...008

What do you think about it?

The statement says n^k will contain at least 6 digits, so don't worry.

Life shouldn't be null.