大数开根

大数开根

科技前沿 • 2025-02-28 20:47 • 阅读 42

大家好，我是讯享网，很高兴认识大家。

口胡

牛顿迭代是一种数值方法，可以快速地求出方程的解。
~~这玩意不一定收敛，然而开根是可以放心的。~~
对于方程 $f (x)$ ，已知一个逼近根的邻点 $x_0$ ，则有
$x_0 - \frac{f(x_0)}{f'(x_0)}$
对于大数 $N$ 开 $p$ 次方根，实际上就是求解方程 $x^p -N = 0$ 。
则牛顿迭代的形式化简之后就是
$\frac{N - x_0^p} {p*x_0^{p-1}} + x_0$

注意事项

牛顿迭代对初值非常敏感，优秀的初值能极大地减少时空开销！

code:

板子题：P2293 [HNOI2004]高精度开根

讯享网

自己写的牛顿迭代版本:

// luogu-judger-enable-o2 // luogu-judger-enable-o2 import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.PrintStream; import java.math.*; import java.util.Scanner; public class Main { 
     private static BigInteger Mysqrt(BigInteger N,int p) { 
     if(N.equals(BigInteger.ZERO)) return BigInteger.ZERO; BigDecimal n = new BigDecimal(N); String str = N.toString(); BigDecimal ans = new BigDecimal(str.substring(0,str.length()/p+1)); BigDecimal tmp = BigDecimal.ONE; BigDecimal P = BigDecimal.valueOf(p); BigDecimal eps = BigDecimal.valueOf(0.1); int len = 2; while(true) { 
     tmp = n.subtract(ans.pow(p)).divide(ans.pow(p-1).multiply(P),len,RoundingMode.HALF_DOWN).add(ans); if(tmp.subtract(ans).abs().compareTo(eps) == -1) break; ans = tmp; } if(ans.compareTo(tmp) >= 0) ans = tmp; BigInteger ret = ans.toBigInteger(); if(ret.pow(p).compareTo(N)>0) ret = ret.subtract(BigInteger.ONE); if(ret.add(BigInteger.ONE).pow(p).compareTo(N)<=0) ret = ret.add(BigInteger.ONE); return ret; } public static void main(String[] args) throws Exception { 
     Scanner cin = new Scanner(System.in); int p = cin.nextInt(); BigInteger n = cin.nextBigInteger(); BigInteger ans = Mysqrt(n,p); System.out.println(ans); } }

讯享网

从meto那里扒的神秘代码：

讯享网// luogu-judger-enable-o2 import java.math.BigInteger; import java.util.Scanner; public class Main { 
     public static void main(String[] args) { 
     Scanner in=new Scanner(System.in); int p=in.nextInt(); BigInteger n=in.nextBigInteger(); System.out.println(sqrt(n,p)); } public static BigInteger sqrt(BigInteger n, int m) { 
     if (n.compareTo(BigInteger.ONE) <= 0 || m <= 1) return n; BigInteger now = n.shiftRight((n.bitLength() - 1) * (m - 1) / m), last; do { 
     last = now; now = last.multiply(BigInteger.valueOf(m-1)).add(n.divide(last.pow(m - 1))).divide(BigInteger.valueOf(m)); } while (now.compareTo(last) < 0); return last; } }

口胡

注意事项

code:

相关推荐