Coefficient Computation (大整数、Java解决)

Coefficient Computation UVALive8265

题意：计算组合数C（n，k）的值并将值按给定的进制输出。

思路：Java大整数类硬上。

PS：刚刚学完Java的大整数类，结果却被Java怎么开数组卡到吐血，直接后果就是少开一题，赛后学长指导后5分钟出题，真酸爽……

包：java.math.*
BigInteger类实现了任意精度的整数运算。
BigDecimal类实现了任意精度的浮点数运算。
读入大整数a：Scanner in = new Scanner(System.in); BigInteger a; a = in.nextBigInteger();

定义大整数类BigInteger a,b;

静态valueOf方法可以将普通的数值转换为大数值：BigInteger a = BigInteger.valueOf(100)
大整数的相加a = a.add(b);表达式为a =a+ b；
大整数的相减a = a.subtract(b);表达式为 a = a - b；
大整数的相乘a = a.multiply(b);表达式为 a = a * b；
大整数的相除a = a.divide(b);表达式为 a = a / b；
大整数的取余a = a.mod(b);表达式为 a = a % b；
大整数的比较a.compareTo(b);如果a与b相等则返回0，如果a大于b返回正数，如果a小于b返回负数；
a.valueOf(100);返回值为100的大整数；
将字符串转换成10进制大整数类型：String s = "100000000000000000000000000000000" ，BigInteger c = new BigInteger(s,10)
其他操作：a.pow(b) = a^b；a.gcd(b) = a和b的最大公约数；a.abs() = a的绝对值；a.negate() = a的取反数；max(),min()；
System.out.println(a.toString(d));将大整数a按d进制输出；

大实数类的运算（实现方法与大整数一样）：

BigDecimal add(BigDecimal other)相加
BigDecimal subtract(BigDecimal other)相减
BigDecimal multiply(BigDecimal other)相乘
BigDecimal divide(BigDecimal other RoundingMode mode) 5.0 相除，必须给出舍入方式RoundingMode.HALF_UP是在学校学习的四舍五入方式
BigDecimal compareTo(BigDecimal other)比较返回值和大整数一样，见上边
static BigDecimal valueOf( long x) 返回值为x的大实数
static BigDecimal valueOf(long x,int scale)返回值为x / 10的scale次方的大实数

好了上代码：

import java.math.*;
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n,k,d,t;
        t = in.nextInt();
        for(int o = 0; o < t; o++)
        {
            n = in.nextInt(); 
            k = in.nextInt();
            d = in.nextInt();
            if(n == 0 || k == 0)
                System.out.println(1);
            else
            {
                BigInteger big = BigInteger.valueOf(n);
                for(int i = n-1; i >= n-k+1; i--)
                {
                    big = big.multiply(BigInteger.valueOf(i));
                }
                BigInteger lit = BigInteger.valueOf(k);
                for(int i = k-1; i > 0; i--)
                {
                    lit = lit.multiply(BigInteger.valueOf(i));
                }
                BigInteger ans = big.divide(lit);
                BigInteger[] temp = new BigInteger[50010];//!!!!!!!!!!!!!!!!!!!!!!!!!开数组
                BigInteger dd = BigInteger.valueOf(d);
                int index = 0;
                while(true)
                {
                    if(ans.compareTo(BigInteger.valueOf(0)) == 0) break;
                    temp[index++] = ans.mod(dd);
                    ans = ans.divide(dd);
                }
                for(int i = index-1; i>=0; i--)
                    System.out.print(temp[i]);
                System.out.println();
            }
        }
    }
}

View Code

大整数类也是一个封装好的类，所以可以开数组，但要注意开数组的格式。