## 10083 - Division

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

### 10083 - Division

I have no idea how to solve the problem 10083 with such big numbers, can you share your ideas with me?

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### 10083 - Division (TLE)

Hello,

I have tried almost (you'll see why in a sec) every optimization i could think of but still got TLE. specifically, I tried:
1. check for a%b!=0 or t=1 or a/b*log10(t)>=99 all of which leads to not an integer
2. check a=0 which gives 0
3. i optimized my exponent method to use a binary search type algorithm where i use something like t^a=(t^(a/2))^2 if a is even, and (t^(a/2))^2*t if a is odd.
4. i computed t^b, then use t^b to compute t^a for optimization

i think if you pass #1, then you are guanrenteed to have an integer result that is less than 100 digits, which must be outputted.

so why am i getting TLE? i could only think of two possibilities: either i got an infinite loop in there somewhere, or that my BigInt methods are way too slow. anyone got any suggestions?

Thanks,

Bugz

nikhil
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

### 10083

10083
what is the idea beeeeeeeee
i can think out none
can Y help me?????

zoranh
New poster
Posts: 8
Joined: Wed Nov 26, 2003 7:23 pm
I've got TLE as well, and here's what I did:

1. checked for special cases (b < a, b = 0, a = 0 -- although problem text says POSITIVE integers --, t = 1) - in each of these cases, result is either integer 0, or is not an integer
2. checked whether (a - b) * log10(t) > 99 - in this case result is has more than 99 digits
3. in other cases, used fastexp to calculate t^a and t^b:
M^N=(M^(N/2)) ^ 2 when N is even
M^N=M * (M^((N-1)/2))^2 when N is odd
After that, just divided big numbers, and got TLE.

However, when I removed division from step #3, I got WA (expected) with time = 0.002, which means that all operations except big number division yield zero time. So, what I'm going to do now is to optimize division as much as I can, as all other operations seem not to be complex at all.

zoranh
New poster
Posts: 8
Joined: Wed Nov 26, 2003 7:23 pm
Well, I finally got it AC in only 0.002 sec, without use of big number division.

To solve the problem, you got to transform the expression to the form:
D(t, a, b) = sum(i=0, a/b - 1) (t^b)^i, where a%b=0

This sum can be further solved recursively:
D(t, a, b) = f(t^b, a/b)
f(x, 1) = 1
f(x, 2k) = (1 + x)*f(x^2, k), k = 1, 2, 3, ...
f(x, 2k + 1) = 1 + x*(1+x)*f(x^2, k), k = 1, 2, 3, ...

Special cases are (test in this particular order):
1. a=b => result=1
2. b=0 => not an integer...
3. a=0 => result=0
4. a%b != 0 => not an integer...
5. t=1 => not an integer...
6. (a - b) * log10(t) > 99 => not an integer...

If none of these conditions is met, then result is an integer with less than 100 digits, and then algorithm above should be used to calculate the result.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
hmmmmmmmmmmmm....
I followed your advice and still got a TLE. its either an infinite loop or my bigInt implementation is too slow then...

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### BigInteger (10083 Division)

Okay, I am asking about 10083 in UVA...
This is a Waterloo local contest question, and their official solution is available on the web, making use of Java BigInt class.

I implemented the exact same way as the official solution did, except using my own big Integer class written in C++ STL (strings)

unfortunately my solution runs way over 10 seconds. I see some people got 0.000 seconds... thats a pretty huge difference...

I only used multiplication and addition for this problem, with the classical implementation (how you would do multiplication/addition by hand). and my BigInt class is pretty correct considering i have used it in about 30 other UVA problems (but I usually see about .5 second difference, not 10)

so does anyone have any suggestions for me?

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Hi!

I remember to have the same problem when I tried to get AC on the problem. But then I realized that the problem was not in the algo of addition and/or multiplication. The bug was that there are test cases when you need to add lots of equal numbers and you shouldn't do that. You should get the answer another way in such cases.

Hope it helps. Bye.
Andrey.

da0321
New poster
Posts: 1
Joined: Sat Mar 05, 2011 7:03 pm

### Re: 10083 - Division

i use zoranh's algorithm, but i have no idea why i always got WA??

Code: Select all

``````#include<iostream>
#include<cmath>

#define digitMax 101

using std::cin;
using std::cout;
using std::endl;

int main(){
int t, a, b;
int ans[digitMax], divisor[digitMax], tmp[digitMax];
int i, j, k, count, bit;

while(cin>>t>>a>>b){
if(a==b){
cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) 1"<<endl;
continue;
}
else if(a==0){
cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) 0"<<endl;
continue;
}
else if(b==0 || a%b!=0 || t==1 || (a-b)*log10(t)>99){
cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) is not an integer with less than 100 digits."<<endl;
continue;
}

for(i=0; i<digitMax; ++i){
divisor[i] = 0;
tmp[i] = 0;
}
count = 1;
divisor = 1;
for(i=0; i<b; ++i){
for(j=0; j<=count; ++j){
divisor[j] *= t;
if(j>0 && divisor[j-1]>9){
divisor[j] += divisor[j-1]/10;
divisor[j-1] %= 10;
if(j==count){
++count;
}
}
}
}

ans = 1;
bit = 1;
for(k=0; k<a/b-1; ++k){
for(j=0; j<count; ++j){
for(i=0; i<bit; ++i){
tmp[i+j] += ans[i]*divisor[j];
}
}
tmp += 1;
bit += count-1;
for(i=1; i<=bit; ++i){
if(tmp[i-1]>9){
tmp[i] += tmp[i-1]/10;
tmp[i-1] %= 10;
if(i==bit){
++bit;
}
}
ans[i-1] = tmp[i-1];
tmp[i-1] = 0;
}
}

cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) ";
for(i=bit-1; i>=0; --i){
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
``````

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### Re: 10083 - Division

zoranh's order is not correct.
The first thing to check should be : if the denominator is zero (t == 1).
There is no test case where t,a,b is less than 1, so no need to check for a == 0 or b == 0.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

### Re: 10083 - Division

it would be great if zoranh (or anyone) helped us by the Mathematical principle behind this conditions to check .... this is why we solve such problems i guess .. to learn predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

### Re: 10083 - Division

I was able to understand all the other conditions except these two :
• if ((a-b)log10(t) + 1 >= 100) -> not an integer
• if (a % b != 0) -> not an integer
can someone please give me mathematical proofs as to why the above two conditions are true.

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

### Re: 10083 - Division

if (a==b) result is 1.

if(t==1 || a<b) result is not an integer;

if(a>b) {

check numberOfDigits is less than 100 using logarithm

else

not an integer less than 100 digits;

}