数学-高精度

kuoying 2020-06-21

1.Integer Inquiry

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1047

解法:一道求大数之和,我们利用java里的BigInteger就可以轻松的解决,不过需要注意下格式的问题,每输出一个就要空一行,最后一个不用

代码:

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static void main(String[] arg)
    {
        Scanner in=new Scanner(System.in);
        int t;
        while(in.hasNext())
        {
            t=in.nextInt();
            while(t-->0)
            {
                BigInteger b=new BigInteger("0");
                while(in.hasNextBigInteger())
                {
                    BigInteger c=new BigInteger("0");
                    c=in.nextBigInteger();
                    if(!c.equals(BigInteger.ZERO))
                    {
                        b=b.add(c);
                    }
                    else
                    {
                        System.out.println(b);
                        if(t!=0)
                            System.out.println();
                        break;
                    }
                }
            }
        }
    }
}

2.Exponentiation

 题目:https://vjudge.net/problem/POJ-1001/origin

解法:这道是一个浮点数的次幂求解,通过java里的BigDecimal的pow方法,即可完成对应的求解。

对于输出有特殊要求,小数点后舍去无意义的0,用到stripTrailingZeros()方法去除所有尾部的0,然后再用toPlainString()将BigDecimal转化为String

之后,在比对转化的字符串的第一个字符是否为“0”,如果为0,则去掉它只保留小数点之后的数,利用substring(1),截取字符串

代码:

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    public static void main(String[] arg)
    {
        Scanner in=new Scanner(System.in);
        while(in.hasNext())
        {
            BigDecimal a=in.nextBigDecimal();
            int k=in.nextInt();
            a=a.pow(k);
            String str=a.stripTrailingZeros().toPlainString();
            if(str.charAt(0)==‘0‘)
                System.out.println(str.substring(1));
            else
                System.out.println(str);
        }
    }
}

3.How many Fibs?

题目:https://vjudge.net/problem/POJ-2413/origin

思路:这是一道求在一定的范围内,包含的斐波那契数的个数。由于范围是10的100次方,因此我们设置大整数数组的长度为10000,足以包括。

代码:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger a[]=new BigInteger[10000];
    public static void main(String[] arg)
    {
        Scanner in=new Scanner(System.in);
        for(int i=0;i<10000;i++)
            a[i]=BigInteger.ZERO;
        a[0]=BigInteger.valueOf(1);
        a[1]=BigInteger.valueOf(2);
        for(int i=2;i<10000;i++)
            a[i]=a[i].add(a[i-1].add(a[i-2]));
        BigInteger b,c;
        while(true)
        {
            b=in.nextBigInteger();
            c=in.nextBigInteger();
            if(b.equals(BigInteger.ZERO)&&c.equals(BigInteger.ZERO))
                break;
            int res=0;
            for(int i=0;i<10000;i++)
            {
                if((a[i].compareTo(b)==1||a[i].compareTo(b)==0)&&(a[i].compareTo(c)==-1||a[i].compareTo(c)==0))
                    res++;
                if(a[i].compareTo(c)==1)
                    break;
            }
            System.out.println(res);
        }
    }
}

4.Segment

 题目:http://acm.hdu.edu.cn/showproblem.php?pid=5666

解法:这是一道求在一个三角形区域内的整数点的个数,不包含在线上的点。通过递推分析,找规律后知道,个数为:(q-1)*(q-2)/2%p

由于q很大,所以我们需要用到大整数来进行求解。

代码:

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
    public static void main(String[] arg)
    {
        Scanner in=new Scanner(System.in);
        int T=in.nextInt();
        while(T-->0)
        {
            BigInteger q=in.nextBigInteger();
            BigInteger p=in.nextBigInteger();
            BigInteger f=q.subtract(BigInteger.valueOf(2));
            BigInteger res=q.subtract(BigInteger.ONE).multiply(f).divide(BigInteger.valueOf(2));
            res=res.mod(p);
            System.out.println(res);
        }
    }
}

5.Problem B

题目:https://vjudge.net/problem/HDU-5686/origin

解法:这应该是百度的某道题,模拟几组数据后发现竟然是一个斐波那契数列,因此就很简单了,N<=200的因此普通的longlong满足不了,我们需要使用BigInteger

代码:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] arg)
    {
        Scanner in=new Scanner(System.in);
        BigInteger a[]=new BigInteger[10000];
        for(int i=0;i<10000;i++)
            a[i]=BigInteger.ZERO;
        a[0]=BigInteger.valueOf(1);
        a[1]=BigInteger.valueOf(1);
        for(int i=2;i<10000;i++)
            a[i]=a[i].add(a[i-1].add(a[i-2]));
        while(in.hasNext())
        {
            int k=in.nextInt();
            if(k>=1&&k<=200)
                System.out.println(a[k]);
        }
    }
}

相关推荐

seasongirl / 0评论 2020-06-05