no tags 

Note: Some tricky testcases were added on Feb. 26th, 2013 and time limit has been changed. All the solutions have been rejudged and some "Accepted" ones got Wrong Answer / Time Limit Exceeded. However, this problem can still be solved by a simple and beautiful solution :)

Ualter is a smart guy, and he loves mathematics and everything related to numbers. Recently his friend Matheus Pheverso showed him a group of H-numbers. Also, his friend told him that, in the Ancient Greek, there H-numbers would be used to create music. This group of numbers can be described in this way:

  • For each integer N, a positive integer A is H-number with N only if: LCM(N, A) = N * A
  • LCM is the Lowest Common Multiple between two numbers.
  • Example 1: N = 20, H-numbers = {1, 3, 7, 9, 11, 13, 17, 19}
  • Example 2: N = 10, H-numbers = {1, 3, 7, 9}

Ualter loves classical music mainly Pachelbel's compositions. In order to achieve his old dream, he's willing to make a version of Canon in D using only H-numbers to create notes. To solve that problem, he needs, for each number N, the number of H-numbers of N that are between 1 and M, inclusive.


You're given an integer Q - the number of queries. Each query consists of two integer N and M. Your task is to find the number of H-numbers of N between 1 and M.


In the first line there's an integer Q (1 <= Q <= 10^5) representing the number of queries. In the next Q lines there are two numbers N, M (1 <= N, M <= 10^5, M < N).


You have to print for each query an integer xi representing the number of H-numbers of N less or equal to M.


20 15
7 3
10 8


hide comments
Bhuvnesh Jain: 2015-12-22 15:51:26

Please suggest some hints to decrease the time required by solution

Bhuvnesh Jain: 2015-12-22 15:09:23

AC in one go...

:.Mohib.:: 2015-08-01 21:06:38

Awesome Problem....Really Worth it...!! :)

Altamir Gomes Bispo Junior [UFSCar]: 2014-03-01 04:26:12

@darryl: the problem setter didn't actually determine any specific presentation order for M or/and N.

nitish rao: 2013-09-14 11:03:34

i'm getting WA :( .. Please look into it. id:10042643 Any corner test cases please??

nitish rao: 2013-09-14 11:03:26

Last edit: 2013-09-14 11:03:54
darryl: 2013-09-03 04:45:37

@problem setter, please check Submission id:9657951. Keep getting WA

Edit: Nevermind, got AC. Are there several testcases where M>=N? Just wondering.

Last edit: 2013-07-17 03:16:14
!!.Nginx.!!: 2013-09-03 04:45:37

getting WA... any tricky test case please tel..

(Tjandra Satria Gunawan)(曾毅昆): 2013-09-03 04:45:37

@Aditya Pande: That's magic ;-) nearly impossible... just find the weakness in test case/constraints :-P

Aditya Pande: 2013-09-03 04:45:37

how can i do better than 0.12s without precomputation...

Last edit: 2013-01-02 07:47:13

Added by:Mateus Dantas [ UFCG ]
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Mateus Dantas