首页 > 专题系列 > Java解POJ > POJ 2539 Division [解题报告] Java
2013
11-11

POJ 2539 Division [解题报告] Java

Division

问题描述 :

Given t, a, b positive integers not bigger than 2147483647, establish whether (t^a – 1)/(t^b -1) is an integer with less than 100 digits.

输入:

Each line of input contains t, a, b.

输出:

For each line of input print the formula followed by its value, or followed by “is not an integer with less than 100 digits.”, whichever is appropriate.

样例输入:

2 9 3
2 3 2
21 42 7
123 911 1

样例输出:

(2^9-1)/(2^3-1) 73
(2^3-1)/(2^2-1) is not an integer with less than 100 digits.
(21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106
(123^911-1)/(123^1-1) is not an integer with less than 100 digits.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
 static BigInteger digit100=new BigInteger("1");
 static int t,a,b;
 static void start(){
	for(int i=0;i< 100;++i)
		digit100 = digit100.multiply(BigInteger.valueOf(10));
 }

 public static void main(String[]args) throws Exception{

  BigInteger num1,num2,temp,ans;
  start();
  //Scanner cin = new Scanner(new FileInputStream("input.txt"));
  Scanner cin = new Scanner(System.in);
		
  while(cin.hasNext()){
	t = cin.nextInt();
	a = cin.nextInt();
	b = cin.nextInt();
	if((t==1||b==0||a< b)){
		output(BigInteger.valueOf(-1));
	}
	else if(a==0){
		output(BigInteger.valueOf(0));
	}
	else if(a==b){
		output(BigInteger.valueOf(1));
	}
	else if(a%b!=0||(a-b)*java.lang.Math.log10((double)t)>120){
		output(BigInteger.valueOf(-1));
	}
	else{
		temp = BigInteger.valueOf(t);
		num1 = temp.pow(a);
		num2 = temp.pow(b);
		num1 = num1.subtract(BigInteger.ONE);
		num2 = num2.subtract(BigInteger.ONE);
		ans = num1.divide(num2);
		if(ans.toString().length()< 100){
			output(ans);
		}else{
			output(BigInteger.valueOf(-1));
		}
	}
   }
 }

 static void output(BigInteger who){
  if(who.equals(BigInteger.valueOf(-1))){
   System.out.println("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) is not an integer with less than 100 digits.");
  }
  else{
   System.out.println("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) "+who);
  }
 }
}

  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。