Power of Twos
Practice
4.4 (7 votes)
Medium
Problem
35% Success 3960 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Little Jhool is friend with the magical creature from Koi Mil Gaya as we all know, called Jaadu.

Now, Jhool is learning Mathematics from Jaadu; he wants to know about the Mathematics of the other planet, too.

In Jaadu's planet, the sequence of powers of two are called the: The \(JP\). (Jaadu power!) That is, \(2^1, 2^2, 2^3.... 2^{1000000}\). \(10,00,000\) being the limit known to the people on Jaadu's planet. Also, Jhool is smart so he notices that this particular sequence starts from index 1 and NOT 0. Now since Jhool thinks that he's understood the sequence well, already so he challenges Jaadu.

Jaadu gives him a number, denoted by N, and asks Jhool to find the number of pairs \((i, j)\) such that \((JP [i] - 1)\) divides \((JP[j] - 1)\) and \(1\le i<j \le N \). Jhool is stunned by this difficult question. And needs your help!

Input:
First line contains number of test cases T. Each test cases contains single integer N.

Output
For each test case print total numbers of pairs \((i,j)\) such that \(1\le i < j \le N\) and \(JP[i]-1\) is divisors of \(JP[j]-1\).

Constraints:
\(1 \le T \le 10000\)
\(1 \le N \le 1000000\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
331 votes
Tags:
Medium
Points:30
49 votes
Tags:
AlgorithmsDynamic ProgrammingSegment Trees
Points:30
9 votes
Tags:
AlgorithmsDynamic Programming