完全平方数 题解

由于练习二分查找 就特意写了二分
首先写一个xppmin寻找第一个比x大的数
然后分两类讨论即可，分l是否为完全平方数讨论计算

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        long num[] = new long[31622];
        int p=0;
        for(long i=1;i<=100000;i++)
        {
            if(p==31622)
                break;
            else{
                num[p++] = i*i;
            }
        }
        for(int i=0;i<n;i++)
        {
             in.nextToken();
             int l = (int)in.nval;
             in.nextToken();
             int r = (int)in.nval;
             if((int)Math.sqrt(l)!=Math.sqrt(l))
                 out.println(xppmin(r,num)-xppmin(l,num));
             else{
                out.println(xppmin(r,num)-xppmin(l,num)+1);
            }
        }
        out.flush();
    }
    public static int xppmin(int x,long num[])//第一个比他大
    {
        int l=0,r=31621,mid = (l+r)>>1;
        while(l<=r)
        {
            mid = (l+r)>>1;
            if(num[mid]>x)
            {
                r = mid-1;
            }
            else if(num[mid]<x)
            {
                l = mid+1;
            }
            else if(num[mid]==x)
                return mid+1;
        }
        return l;
    }
                  }