首页 > 代码库 > poj2109 这货是大数么

poj2109 这货是大数么

2024-07-19 22:50:44   218人阅读

你以为它是大数,但实际上它不是

我觉得这应该是种可正常的姿势了

import java.math.BigInteger;import java.util.Scanner;public class Main {	static BigInteger p,l,r,div;	static int n;	public static int cmp(BigInteger mid){		BigInteger sum=mid.pow(n);		return sum.compareTo(p);	}	public static BigInteger calc(){		l=BigInteger.ZERO;		r=BigInteger.valueOf(1000000000);		BigInteger div=BigInteger.valueOf(2);		while(l.compareTo(r)<0){			BigInteger mid=l.add(r).divide(div);			int fl=cmp(mid);			if(fl==0){				return mid;			}			else if(fl==-1){				l=mid.add(BigInteger.ONE);			}			else r=mid;		}		return r;	}	public static void main(String args[]){		Scanner scanner=new Scanner(System.in);		while(scanner.hasNext()){			n=scanner.nextInt();			p=scanner.nextBigInteger();			BigInteger ans=calc();			System.out.println(ans);		}	}}

　但wa

有种更为优雅的姿势

#include <cstdio>#include <cmath>int main(){    double n , m ;    int ans ;    while ( scanf( "%lf%lf" , &m , &n ) != EOF )          printf( "%.0f\n" , exp(log(n)/m) ) ;   }

感动地五体投地

另附大神证明思路:泰勒公式证明相差不会超过9

http://blog.csdn.net/synapse7/article/details/11672691

经过无聊的改动

import java.math.BigInteger;import java.util.Scanner;public class Main {    static BigInteger p,l,r,div;    static int n;    public static int cmp(BigInteger mid){        BigInteger sum=mid.pow(n);        return sum.compareTo(p);    }    public static BigInteger calc(){        l=BigInteger.ZERO;        r=BigInteger.valueOf(1000000000);        BigInteger div=BigInteger.valueOf(2);        while(l.compareTo(r)<0){            BigInteger mid=l.add(r).divide(div);            int fl=cmp(mid);            if(fl==0){                return mid;            }            else if(fl==-1){                l=mid.add(BigInteger.ONE);            }            else r=mid;        }        int fl=0;        if((fl=cmp(r))==0)return r;        if(fl==-1){            while(p.subtract(r.pow(n)).compareTo(BigInteger.ONE)>0)r=r.add(BigInteger.ONE);            return r;        }        else {            while(r.pow(n).subtract(p).compareTo(BigInteger.ONE)>0)r=r.subtract(BigInteger.ONE);            return r;        }    }    public static void main(String args[]){        Scanner scanner=new Scanner(System.in);        while(scanner.hasNext()){            n=scanner.nextInt();            p=scanner.nextBigInteger();            BigInteger ans=calc();            System.out.println(ans);        }    }}

 

poj2109 这货是大数么


联系
我们