posts - 64, comments - 4, trackbacks - 0, articles - 0

harbin网络预选赛1003

Posted on 2010-09-11 17:33 acronix 阅读(150) 评论(0)  编辑 收藏 引用 所属分类: zhaoboqiang解题报告

用Java二分开方

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

public class Main {
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        BigInteger y ;
        String s;
        s=cin.next();
        while(!s.equals("#")){
            if(s.equals("0")){
                System.out.println(0);
                s=cin.next();
                continue;
            }
            y=new BigInteger(s);
            BigInteger max = y;
            BigInteger min = BigInteger.ONE; 
            BigInteger two = new BigInteger("2"); 
            BigInteger avg = BigInteger.ZERO; 
            BigInteger lastAvg = null; 
            while(!avg.equals(lastAvg)) { 
                lastAvg = avg; avg = max.add(min).divide(two); 
                int res = avg.multiply(avg).compareTo(y); 
                if(res == 0) break; 
                if(res > 0) max = avg; 
                else min = avg; 
            } 
            int a[]=new int[10010];
            int pt=0;
            while(!avg.equals(BigInteger.ZERO)){
                a[pt]=avg.mod(BigInteger.valueOf(2)).intValue();
                avg=avg.divide(BigInteger.valueOf(2));
                pt++;
            }
            for(int i=pt-1;i>=0;i--){
                System.out.print(a[i]);
            }
            System.out.println();
            s=cin.next();
        }
    }
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理