洛谷 - P2293 - 高精度开根

https://www.luogu.org/problemnew/show/P2293

要求求出给定高精度整数的非负根取整的结果。

还有神仙用Python的浮点pow运算骗到不少分的。

唉！

那么我们使用保险的语言：Java，需要怎么做呢？

高精度数是10的10000次方，他的根应该在10的100次方附近？（题目没说是平方根啊，乱搞！）

我们先读入一个String，数出String有多少位，在这个位数的左右至多4位范围进行二分答案。

自己瞎搞了很久，不是T就是M的，还以为是语言的劣势。

其实是自己的二分的范围过大了。（至少限制一下r，当k比较大的时候r是很小的，k比较大的时候大数的乘方运算开销大，节省的时间就多很多了）

像神仙那样先用logn缩小范围就挺好内存80MB，速度是2.5秒。

由于跑得飞快，实际上还可以加入cnt-gc大法。设置cnt模100，内存降至40MB，速度是4秒。

但是Python只需要0.5秒和4MB哦！据说是因为Python的底层是用C语言实现的！（但是不限制二分范围也只是比Java多过一个点）

（还好大部分icpc应该对每种语言是公平的）

import java.util.*;

import java.math.*;

public class Main {

    static int k;

    static BigInteger n;

    public static void main(String args[]) {

        Scanner sc=new Scanner(System.in);

        k=sc.nextInt();

        n=sc.nextBigInteger();

        if(k==1) {

            System.out.println(n);

            return;

        }

        BigInteger l=BigInteger.ZERO,r=BigInteger.ONE;

        while(r.pow(k).compareTo(n)<=0) {

            l=r;

            r=r.shiftLeft(1);

        }

        BigInteger m=null;

        while(l.add(BigInteger.ONE).compareTo(r)<0) {

            m=(l.add(r)).shiftRight(1);

            int res=m.pow(k).compareTo(n);

            if(res<=0) {

                l=m;

            }

            else {

                r=m;

            }

            //System.gc();

        }

        if(l.pow(k).compareTo(n)<=0)

            System.out.println(l);

        else

            System.out.println(r);

        sc.close();

    }

}

巴特西

洛谷 - P2293 - 高精度开根 - 高精度

最新文章

热门文章