dipu-and-interesting-numbers-2

Little Dipu is a small kid and like all the other kids, he likes to play, but he plays with numbers (He is extraordinary you know). Now-a-days Dipu has some extra interest in odd numbers. So, he says that a number N is interesting if it has odd number of divisors. Now Dipu turns to you and asks you to tell him how many interesting numbers are there between two given numbers, L and R (both inclusive).
 Input 
First line of input contains the number of test cases T. Each of the next T lines contains two space separated integers L and R.

 Output 
For each test case, output an integer, denoting the count of interesting numbers between L and R (both inclusive).

 Constraints 
1 ≤ T ≤ 100000

1 ≤ L ≤ R ≤ 10^18

SAMPLE INPUT
2
1 3
6 10

SAMPLE OUTPUT
1
1

Explanation

In 1st test case, 1 has 1 divisor, 2 has 2 divisors and 3 also has 2 divisors. So only 1 has odd number of divisors. Hence count of interesting numbers is 1.

In 2nd test case, 9 is the only number to have odd number of divisors. So answer is again 1.

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Sorting

Mathematics


Solutions:
def interestingNumbers1():
	tests = int(input())
	for t in range(tests):
		count = 0
		l, r = list(map(int, input().split()))
		sl, sr = int(l**0.5), int(r**0.5)
		if sl**2 > l:
			sl = sl - 1
		if sr**2 > r:
			sr = sr - 1
		print(sr-sl+ (sl**2 == l))

interestingNumbers1()


# -*- coding: utf-8 -*-

def calc(x):
	ans = 0    
	L = 1
	R = 10**9
	while(L<=R):
		M = (L+R)>>1
		if(M*M<=x):
			ans = M
			L = M + 1
		else:
			R = M - 1
	return ans

t = int(eval(input()))

for i in range(t):
	l,r = list(map(int,input().split()))
	fs = calc(l)
	if(fs*fs!=l):
		fs+=1
	sc = calc(r)
	print(sc-fs+1)


import math
def perfectSqrCount(start,end):
	start_sqrt=int(math.sqrt(start))
	end_sqrt=int(math.sqrt(end))
	if start_sqrt * start_sqrt!= start:
		start_sqrt+=1
	if end_sqrt * end_sqrt> end:
		end_sqrt-=1	
	return (end_sqrt-start_sqrt+1)

test=int(input())

for i in range(test):
        line=str(input())
        val=line.split(' ')
        number=perfectSqrCount(int(val[0]),int(val[1]))
        print(number)


import math
noT = input()
for _ in range(int(noT)):
	L,R = list(map(int, input().split(" ")))
	LN   = math.sqrt(L)    
	if int(LN) * int(LN) == L:
		LN = int(LN)
	else:
		LN = int(LN)+1
		
	RN = int(math.sqrt(R))
	if RN * RN > R:
		RN-= 1
	print(int(math.ceil(RN+1-LN)))    
		
		
	
	


import math as mt
times=eval(input())
for _ in range(times):
	inp=input()
	lst=inp.split()
	start=int(lst[0])
	
	end=int(lst[1])
	
	first=mt.sqrt(start)
	
	last=int(mt.sqrt(end))
	
	new=int(first)
	
	if(new*new==start): # for big numbers the floor/ceiling function is already used in python as per 				               
		first=new		# convenience, hence manual check included instead of
	else:				# if new==first
		first=new+1
	if last*last>end:  	# 999999999999999972 ceiling used, so result was incremented by 1
		last-=1
	number=last+1-first
	print(number) 
    
    
    
    
    
    
  
	
		
		
	


import math as mt
times=eval(input())
for _ in range(times):
	inp=input()
	lst=inp.split()
	start=int(lst[0])
	
	end=int(lst[1])
	
	first=mt.sqrt(start)
	
	last=int(mt.sqrt(end))
	
	new=int(first)
	
	if(new*new==start): # for big numbers the floor/ceiling function is already used in python as per 				               
		first=new		# convenience, hence manual check included instead of
	else:				# if new==first
		first=new+1
	if last*last>end:  	# 999999999999999972 ceiling used, so result was incremented by 1
		last-=1
	number=last+1-first
	print(number)
    
    
    
    
    
    
  
	
		
		
	


import math as mt
times=eval(input())
for _ in range(times):
	inp=input()
	lst=inp.split()
	start=int(lst[0])
	
	end=int(lst[1])
	
	first=mt.sqrt(start)
	
	last=int(mt.sqrt(end))
	
	new=int(first)
	
	if(new*new==start):
		first=new
	else:
		first=new+1
	if last*last>end:
		last-=1
	number=last+1-first
	print(number)
    
    
    
    
    
    
  
	
		
		
	


import math
t=eval(input())

def isqrt(n):
	x=1
	y=(x+n/x)/2
	while abs(y-x)>1:
		x=y
		y=(x+n/x)/2
	while y**2>n:
		y-=1
	return y	

for i in range(t):
	l,r=list(map(int,input().split()))
	x=isqrt(l)
	if x**2==l:
		print(isqrt(r)-x+1)
	else:
		print(isqrt(r)-x)


import math
import decimal
t= int(input())
for x in range(t):
	a, b = input().split()
	a, b = int(a), int(b)
	print(int(decimal.Decimal(b).sqrt())-int(decimal.Decimal(a-1).sqrt()))


from math import *
from decimal import *
for _ in range(int(input())):
	l,r=list(map(Decimal,input().split()))
	l=Decimal(l)
	r=Decimal(r)
	p=int(l.sqrt())
	q=int(r.sqrt())
	if Decimal(p**2)==l:
		p-=1
	print(q-p)


import sys
def xqrt(n):
	lo,hi = 0,1000000000
	while(lo<hi):
	mid=(lo+hi+1)/2
	if(mid*mid<=n):
	    lo=mid
	else:
	    hi=mid-1
	return lo
for _ in range(eval(input())):
	L,R=list(map(int,input().split()))
	x,y=-1,-1
	rt=xqrt(L)
	if(rt*rt == L):
	x=rt
	elif(rt+1)*(rt+1) <=R :
	x=rt+1
	rt=xqrt(R)
	if(rt*rt>=L):
	y=rt
	if(x==-1 and y==-1):
	print("0")
	else:
	print(y-x+1)
	


from sys import stdin
import decimal as m
t = int(stdin.readline())
m.getcontext().prec = 20
for i in range(t):
	l,r = list(map(int, stdin.readline().split()))
	lt = m.Decimal(l).sqrt();
	lsq, rsq = int(m.Decimal(l).sqrt()), int(m.Decimal(r).sqrt())
	if lsq**2 < l:
		lsq+=1
	if lsq<=rsq:
		lsq = rsq-lsq+1
	else:
		lsq = 0
	print(lsq)