I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first.
The problem is straight for you have and 3 integers $t$, $a$ and $b$, greater or equal than $0$ and less or equal than $2^{31} - 1$. Your job is simple, print the integer part of $\frac{t^a-1}{t^b-1}$ if the original number doesn't exceed 100 digits.
At first I think "It would be easy", I'll just check some tricky cases (like a = b or t = 0 or b=0 or a=0) and apply logarithms (to count the digits) if $(a-b)*\log(t) > 99$ then don't print else print the integer part.
But the problem (at least for me) here is know if $\frac{t^a-1}{t^b-1}$ doesn't exceed 100 digits including the fractional part.
Test case: $t = 2; a = 3; b = 2;$ then $\frac{t^a-1}{t^b-1}=\frac{2^3-1}{2^2-1}=\frac{7}{3}=2.333333...$ witch obviously have more than 100 digits.
After searching a little bit I found this page and if you take a look it's just matter of check some cases, that I have already checked except for this one if a % b != 0
then not a integer with less than 100 digits.
I put that condition in my code and It worked! But I'm a want a simple (if possible) explanation of why $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$.
Update: Full and accepted code here:
import java.io.*; import java.math.BigInteger; public class Main { private static BigInteger f(BigInteger x, BigInteger k){ if(k.equals(BigInteger.ONE)) return BigInteger.ONE; if(k.testBit(0)){ return (x.add(BigInteger.ONE).multiply(f(x.pow(2), k.divide(new BigInteger("2"))))).multiply(x).add(BigInteger.ONE); } else{ return x.add(BigInteger.ONE).multiply(f(x.pow(2), k.divide(new BigInteger("2")))); } } private static String D(long t, long a, long b){ BigInteger T = new BigInteger(t+""); BigInteger A = new BigInteger(a+""); BigInteger B = new BigInteger(b+""); return f(T.pow((int)b), A.divide(B)).toString(); } public static void main(String[] args) { BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); String line; String lines[]; long a, b, t; try{ while(true){ line = input.readLine(); if(line == null) break; lines = line.split("[ ]+"); t = Long.parseLong(lines[0]); a = Long.parseLong(lines[1]); b = Long.parseLong(lines[2]); System.out.print("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) "); if(t == 1) System.out.print("is not an integer with less than 100 digits.\n"); else if(a == b) System.out.print("1\n"); else if(b == 0) System.out.print("is not an integer with less than 100 digits.\n"); else if(a == 0) System.out.print("0\n"); else if(a % b != 0) System.out.print("is not an integer with less than 100 digits.\n"); else if((a - b)*Math.log10((double)t) > 99f) System.out.print("is not an integer with less than 100 digits.\n"); else System.out.print(D(t, a, b)+"\n"); } } catch(IOException e){} }
}