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

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

10083 - Division

Post by Shahab »

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

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

10083 - Division (TLE)

Post by bugzpodder »


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?



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


Post by nikhil »

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

New poster
Posts: 8
Joined: Wed Nov 26, 2003 7:23 pm

Post by zoranh »

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.

New poster
Posts: 8
Joined: Wed Nov 26, 2003 7:23 pm

Post by zoranh »

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.

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

Post by bugzpodder »

I followed your advice and still got a TLE. its either an infinite loop or my bigInt implementation is too slow then...

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

BigInteger (10083 Division)

Post by bugzpodder »

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

Post by Andrey Mokhov »


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. :roll:


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

Re: 10083 - Division

Post by da0321 »

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

Code: Select all


#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;
			cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) 1"<<endl;
		else if(a==0){
            cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) 0"<<endl;
		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;
		for(i=0; i<digitMax; ++i){
			divisor[i] = 0;
			tmp[i] = 0;
		count = 1;
		divisor[0] = 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;
		ans[0] = 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[0] += 1;
			bit += count-1;
			for(i=1; i<=bit; ++i){
					tmp[i] += tmp[i-1]/10;
					tmp[i-1] %= 10;
				ans[i-1] = tmp[i-1];
				tmp[i-1] = 0;
        cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) ";
		for(i=bit-1; i>=0; --i){
	return 0;

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

Re: 10083 - Division

Post by fh »

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:
Felix Halim

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

Re: 10083 - Division

Post by Ahmad »

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 :)

New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 10083 - Division

Post by predicate »

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.

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

Re: 10083 - Division

Post by Muftee_Ruet »

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


not an integer less than 100 digits;


Post Reply

Return to “Volume 100 (10000-10099)”