POJ 1405 貪心+找規律+高精度 in JAVA

每次都要剩盡可能少 就是找盡可能的小的分母

典型的貪心

找規律可以發現

答案序列是這樣的：

2 3 7 43.。。

3=1*2+1

7=2*3+1（這裡的2來自上式的1*2）

43=6*7+1（這裡的6來自上式的2*3）

...

别小看這個簡單的關系 接管隻需要遞推18次，但是數大的吓人，如果不用BigInteger就隻能用字元串了。

這就是用到高精度的地方。有點非典型。

這道題險過，TL是1000M，一開始900多，改了改還是有800多。。

JAVA 代碼如下：

import java.io.*;

import java.math.*;

import java.util.*;

class Main

{

public static void main(String[] args)

{

BigInteger[] answer = new BigInteger[18];

BigInteger temp = BigInteger.valueOf(2);;

answer[0] = BigInteger.valueOf(2);

BigInteger one = BigInteger.valueOf(1);

Scanner cin = new Scanner(new BufferedInputStream(System.in));

int n = cin.nextInt();

System.out.println(answer[0]);

for(int i = 1;i < n;i++)

{

answer[i] = temp.add(one);

temp = temp.multiply(answer[i]);

System.out.println(answer[i]);

}

}

}